[BOJ] 2606. 바이러스

 

캡스톤, 기말 등 각종 이벤트들로 인해 그동안 백준을 많이 풀지 못하였는데 쉬운 것부터 다시 복습하고자 정리해보았다.

이전 포스트와 같이 인접 행렬, 인접리스트, 그래프 형태로 풀이해보았다.

 

문제

 

 

문제를 통해 탐색을 시작할 정점의 번호가 1번부터 시작한다는 것을 알 수 있다.

 

 

입력 예제

 

 

 

문제 풀이

 

입력 예제를 참고하여 아래와 같이 그래프를 그리고, 그에 따른 인접리스트와 각 노드 별 연결 상태를 나타내는 행렬을 그려보았다.

BFS 기준으로 탐색을 진행하였을 때에는 1, 2, 5, 3, 6의 순서로 이동하고, 이 때 바이러스에 걸리게 되는 컴퓨터의 수는 1번 컴퓨터를 제외한 4개이다. 이러한 연결 및 탐색 정보를 통해 BFS로 풀면 간단하게 풀리겠구나를 짐작하고 코드로 옮겨보았다.

 

 

 

 

 

 

인접 리스트 풀이

 

public class BOJ2606_ArrayList {
    static int n, m, result;
    static ArrayList<Integer> [] arr;
    static boolean[] visited;

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

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        arr = new ArrayList[n+1];

        for (int i=0; i<=n; i++) {
            // 인접 리스트 초기화
            arr[i] = new ArrayList<Integer>();
        }

        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 양방향 연결
            arr[x].add(y);
            arr[y].add(x);
        }

        Arrays.fill(visited, false);
        BFS(1, 0); // 탐색 시장할 정점 번호
        System.out.println(result);
    }

    public static void BFS(int index, int cnt) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        
        while (!queue.isEmpty()) {
            int curr = queue.poll();
			for (int i: arr[curr]) {
                // 방문 조건: 아직 방문하지 않은 상태일 때
                System.out.println("i = " + i);
                if (!visited[i]) {
                    result += 1;
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
        
    }
}

 

 

 

 

 

그래프 풀이

public class BOJ2606_Graph {

    static int n, m, result;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();
        visited = new boolean[n+1];

        for (int i=0; i<=n; i++) {
            // 그래프 초기화
            graph.add(new ArrayList<>());
        }

        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 그래프 간 양방향 연결
            graph.get(x).add(y);
            graph.get(y).add(x);
        }

        Arrays.fill(visited, false);
        BFS(1, 0); // 탐색 시장할 정점 번호
        System.out.println(result);
    }

    public static void BFS(int index, int cnt) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int i: graph.get(curr)) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    result += 1;
                }
            }
        }
    }
}

 

 

 

 

인접 행렬 풀이

public class BOJ2606_Array {
    static int n, m, result;
    static int[][] arr;
    static boolean[] visited;

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

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        arr = new int[n+1][n+1];
        visited = new boolean[n+1];

        for (int i=0; i<m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            // 양방향 연결
            arr[x][y] = arr[y][x] = 1;
        }

        Arrays.fill(visited, false);
        BFS(1, 0);
        System.out.println(result);
    }

    public static void BFS(int index, int cnt) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            for (int i=1; i<=n; i++) {
                // 방문 조건
                if (!visited[i] && arr[curr][i] == 1) {
                    queue.add(i);
                    visited[i] = true;
                    result += 1;
                }
            }
        }
    }
}