DFS - BOJ2606 "바이러스"

문제 링크

초등학교 진학 완료!

---

풀이 (정답)

public static class BOJ2606 {

        static ArrayList<Integer>[] edges; // 노드간의 연결을 나타내는 인접 리스트

        static boolean[] visited; // 방문 여부 판별(노드별)

        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            StringTokenizer st;

            int M = Integer.parseInt(br.readLine()); // 총 컴퓨터 개수 == node
            int N = Integer.parseInt(br.readLine()); // 총 연결 개수 == edge

            edges = new ArrayList[M + 1];

            visited = new boolean[M + 1]; // 1번 컴퓨터부터 시작하기 위해 0번 버림

            Arrays.fill(visited, false); // false 로 초기화

            for (int i = 1; i < M + 1; i++) { 
            // N+1 부터 시작하기 위해, edges 의 초기화 (1부터)
                edges[i] = new ArrayList<>();
            }

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());

                edges[start].add(end);
                edges[end].add(start); // 양방향 추가
            }

            dfs(1); // 항상 1번노드로 dfs 수행

            int count = 0;

            for (boolean b : visited) {
                if (b) count++;
            }

            System.out.println(count - 1); // 자기 자신을 제외하므로
        }

        public static void dfs(int node){
            visited[node] = true;

            for (Integer integer : edges[node]) { // 1번과 연결된 노드들 순회
                if (visited[integer]) continue;
                dfs(integer);
            }
        }
    }

• dfs를 통해서 쭉쭉!
• 노드간의 인접 리스트를 만들고 (edges)
• 처음 노드는 무조건 1이므로 , 1로 dfs 시작한다
• dfs 하면서 내려가고, 완전 탐색의 필요는 없으므로 dfs는 1만 수행한다
• 마지막에 visited[] 배열의 요소 중 true인 녀석들은 "방문한" 노드들이다.
• 1을 포함하므로, -1 해준다 ( 문제에서는 1번 노드가 "감염시킨" 노드들을 리턴하라고 했으니 )