[백준(Baekjoon)] 2606. 바이러스 (java, BFS)

안녕하세요. 오늘은 백준의 2606. 바이러스 문제를 풀어보겠습니다.

문제 링크

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

문제 풀이

✔ 입력받은 연결 쌍으로 map 2차원 배열 생성

네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍들을 입력 받은 후, 그 쌍들을 토대로 2차원 배열인 map을 만듭니다.
예를 들어 번호쌍이 (1 7) 이렇게 입력되었으면 1번과 7번이 서로 연결되어있다는 뜻이므로, map[1][7] = 1, map[7][1] = 1 이렇게 저장해줍니다.

✔ bfs로 만들어진 map을 돌면서 연결되어있는지 확인하기

bfs로 만들어진 map을 돌면서 연결되어있는지 확인해줍니다. map[i][j]가 1이면(서로 연결되어 있으면) 이를 방문하면 됩니다.!

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int computer = Integer.parseInt(br.readLine());
        int network = Integer.parseInt(br.readLine());
        
        int[][] line = new int[network][2];
        
        for(int i = 0; i < network; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            //문제에서는 노드 번호가 1부터 주어지는데, 배열은 index가 0부터여서 임의로 1을 빼준다
            line[i][0] = Integer.parseInt(st.nextToken())-1;
            line[i][1] = Integer.parseInt(st.nextToken())-1;
        }
        
        boolean[] visited = new boolean[computer];
        int[][] map = new int[computer][computer];
        
        for(int i = 0; i < network; i++) {
            int c = line[i][0];
            int r = line[i][1];
            
            map[c][r] = 1;
            map[r][c] = 1;
        }
        
        for(int i = 0; i < computer; i++) {
            map[i][i] = 1;
        }
        
        int answer = bfs(computer, visited, map, 0);
        
        System.out.println(answer);
    }
    
    private static int bfs(int computer, boolean[] visited, int[][] map, int sr) {
        
        int cnt = 0;
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(sr);
        visited[sr] = true;
        
        while(!q.isEmpty()) {
            int node = q.poll();
            
            for(int i = 0; i < computer; i++) {
                if(map[node][i] != 1 || visited[i] == true) {
                    continue;
                }
                
                q.add(i);
                visited[i] = true;
                cnt++;
            }
        }
        
        return cnt;
    }
}

느낀점

이전에 풀었던 미로 탐색 문제와 비슷해서 상대적으로 쉽게 풀었던 것 같다.