[백준]JAVA - 2606번: 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

풀이

해당 문제는 dfs, bfs 어떤 방법을 사용하던지 풀리는 문제인데 필자는 bfs를 이용해서 풀었다.

 

서로 연결된 컴퓨터를 저장하기 위해 int형 배열 map을 생성해주고, 해당 배열에 map[출발지][도착지] = 1, map[도착지][출발지] = 1을 입력해준다.

for (int i=0; i<K; i++) {
    st = new StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken()); // 시작
    int e = Integer.parseInt(st.nextToken()); // 도착
			
    map[s][e] = 1;
    map[e][s] = 1;
}

이 문제는 단방향으로 연결된 것이 아닌 양방향으로 연결되어 있기 때문에 두 가지 모두 연결되었다고 명시해야한다. 예를 들어 컴퓨터 1과 컴퓨터 3이 연결되었다고 가정하면 1 → 3 과 3 → 1 이 동일하다는 뜻이다.

 

나머지는 딱히 주의할 점이 없다고 생각한다. 모든 bfs 문제와 동일하게 Queue를 생성하고 시작노드(1)을 넣어주면 된다. 그리고 방문여부를 따지면서 cnt를 늘려줬다. 물론 출발점인 1은 인접 노드 개수에서 카운팅하지 않으므로 제외시켰다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine()); // 컴퓨터의 수
        int K = Integer.parseInt(br.readLine()); // 직접 연결되어 있는 쌍의 수
        int[][] map = new int[N+1][N+1];
        boolean[] visited = new boolean[N+1];
		
        for (int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 시작
            int e = Integer.parseInt(st.nextToken()); // 도착
			
            map[s][e] = 1;
            map[e][s] = 1;
        }	
		
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
		
        while (!q.isEmpty()) {
            int now = q.poll();
			
            for (int i=1; i<N+1; i++) {
                if (map[now][i] == 1 && visited[i] == false) {
                    if (i == 1) continue;
                    
                    q.add(i);
                    cnt++;
                    visited[i] = true;
                }
            }
        }
		
        System.out.println(cnt);
    }
}