[백준] 바이러스 (2606번)

문제 이해

• 이 문제는 DFS(깊이 우선 탐색)을 사용해 1번 노드와 연결된 모든 노드의 개수를 찾는 문제입니다.
• 주어진 그래프는 무방향 그래프입니다. 즉, 노드 A와 B가 연결되어 있으면 A → B와 B → A로 이동할 수 있습니다.

 

핵심 아이디어

1. DFS(깊이 우선 탐색):
   • DFS는 재귀 호출을 사용해 그래프를 깊이 있게 탐색합니다.
   • 방문한 노드를 추적하며 이미 방문한 노드를 다시 탐색하지 않도록 해야 합니다.
2. 인접 리스트 사용:
   • 그래프를 인접 리스트로 구현합니다. 각 노드는 연결된 노드들의 리스트를 가집니다.
3. 방문 배열 활용:
   • 중복 방문을 방지하기 위해 visit[] 배열을 사용합니다.
   • 탐색 중 방문하지 않은 노드만 재귀적으로 탐색합니다.

 

알고리즘 흐름

1. 입력 받기:
   • 노드와 간선의 개수를 입력받습니다.
   • 각 간선의 정보를 입력받아 그래프(인접 리스트)를 구성합니다.
2. DFS 탐색 시작:
   • 1번 노드에서 출발하며, 방문한 노드를 count 변수로 추적합니다.
3. DFS 탐색 종료 후 결과 출력:
   • 1번 노드와 연결된 모든 노드의 개수를 출력합니다.

 

---

정답은 더보기 클릭

import java.util.*;  // Scanner와 List 사용을 위한 라이브러리

class Main {

    // 그래프를 인접 리스트로 표현 (각 노드의 연결된 노드를 저장)
    static List<Integer>[] graph;
    static int count = 0;  // 방문한 노드 수를 세기 위한 변수
    static boolean[] visit;  // 방문 여부를 체크할 배열

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in); 

        // 노드의 개수 입력
        int n = in.nextInt();
        in.nextLine();

        // 간선의 개수 입력
        int link = in.nextInt();
        in.nextLine();

        // 그래프 초기화 (노드는 1부터 시작하므로 n+1 크기로 생성)
        graph = new ArrayList[n + 1];
        visit = new boolean[n + 1];  // 방문 여부 배열 초기화

        // 각 노드에 해당하는 ArrayList 초기화
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 입력받기 (노드 간의 연결 정보)
        for (int i = 0; i < link; i++) {
            String[] tmp = in.nextLine().split(" ");  // 간선 정보 입력
            int node1 = Integer.parseInt(tmp[0]);
            int node2 = Integer.parseInt(tmp[1]);

            // 무방향 그래프이므로 양쪽 노드에 서로를 추가
            graph[node1].add(node2);
            graph[node2].add(node1);
        }

        // 시작 노드(1번)를 방문 처리하고 DFS 탐색 시작
        visit[1] = true;
        dfs(1);

        // 1번 노드와 연결된 노드의 개수 출력
        System.out.println(count);
    }

    // DFS(깊이 우선 탐색) 함수
    public static void dfs(int curNode) {
        // 현재 노드와 연결된 모든 노드를 탐색
        for (int i = 0; i < graph[curNode].size(); i++) {
            int nextNode = graph[curNode].get(i);  // 다음 노드 가져오기

            // 다음 노드가 방문되지 않았다면 탐색 수행
            if (!visit[nextNode]) {
                visit[nextNode] = true;  // 방문 처리
                dfs(nextNode);  // 다음 노드로 재귀 호출
                count++;  // 방문한 노드 수 증가
            }
        }
    }
}