[BOJ] 2606 바이러스 (DFS)

문제 출처: https://www.acmicpc.net/problem/2606

 

풀이법: 인접행렬을 이용한 dfs 알고리즘으로 풀었다.

 

Comment: 1) class 이름을 Main으로 하지 않으면 컴파일 에러가 난다.

                  2) 인접행렬은 사이즈에 + 1 만큼 행, 열을 생성하는게 편리하다. (방문 노드 체크 행렬도 마찬가지)

                       -> 이유? : 행렬의 인덱스는 0으로 시작하는 반면에 코테 문제에서 나오는 그래프에선 0번 노드가 잘 등장하지 않기 때문.

 

코드:

import java.util.*;

public class Main {
	
	public static int count = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		int nodeCnt = 0;
		int conCnt = 0;
		
		
		nodeCnt = sc.nextInt();
		conCnt = sc.nextInt();
		//System.out.printf("%d %d\n", nodeCnt,conCnt);

		
		int[][] adjMat = new int[nodeCnt + 1][nodeCnt + 1];
		
		for(int i = 0; i < nodeCnt; i++) {
			for(int j = 0; j < nodeCnt; j++) {
				adjMat[i][j] = 0;
			}
		}
		
		
		for(int i = 0; i < conCnt; i++) {
			int idx = sc.nextInt();
			int jdx = sc.nextInt();
			//System.out.printf("연결 상태 %d %d\n", idx,jdx);
			adjMat[idx][jdx] = 1;
			adjMat[jdx][idx] = 1;	
		}
		
		int[] visited = new int[nodeCnt+1];

		for(int i = 0; i < nodeCnt; i++) {
			visited[i] = 0;
		}
		
		dfs(adjMat, visited, 1);
		
		System.out.print(count);
		
		
	}
	
	public static void dfs(int[][] adjMat, int[] visited, int node) {
		visited[node] = 1;
		//System.out.println(node + " ");
		
		for(int i = 1; i < adjMat[0].length; i++) {
			if(adjMat[node][i] == 1 && visited[i] == 0) {
				dfs(adjMat, visited, i);
				count ++;
			}
		}
		
	}
	
	

}