• 문제 링크: https://www.acmicpc.net/problem/2606

설명

주의할 점

• 컴퓨터 초기화할 때 양방향을 오고갈 수 있다.
• 바이러스의 시작은 1번이다.
• 배열 초기화 할 때, 컴퓨터는 1번부터 시작되니 N+1로 해야한다.

• 컴퓨터 수, 크기의 2차원 배열을 만든다.
  • 노드 연결 관계가 있는 것을 true로 초기화한다.
• 방문할 Queue를 생성한다.
• 바이러스의 시작은 1번 컴퓨터이다. 방문 Queue에 집어넣고, 방문 표시를 한다.
• 방문 Queue 크기가 0이 될 때까지 반복한다.
  • 방문 Queue에서 첫번째 원소를 뽑는다.
  • 반복문을 돌면서 방문하지 않았거나, 채워져있는 부분(true)을 Queue에 집어넣고 바이러스 count를 1씩 증가한다.

코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2606 {
	static int N, M;
    static boolean[][] computer;
    
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BuffereReader(new InputStreamReader(System.in));
        
        StringTokenizer str;
        
        int count = 0;
        
        // 컴퓨터 수
        N = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        // 노드 수
        M = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());
        
        computer = new boolean[N + 1][N + 1];
        boolean[] visited = new boolean[N+1];
        
        // 컴퓨터 초기화
        for (int i = 0; i < M; i++) {
        	str = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Inteber.parseInt(str.nextToken());
            
            computer[a][b] = true;
            computer[b][a] = true;
		}
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;
        
        while (!queue.isEmpty()) {
        	int start = queue.poll();
            
            for(int i = 1; i <= N; i++) {
            	// visited[] => 컴퓨터 방문 배열
            	if(!visited[i] && computer[start][i]) {
                	queue.add(i);
                    visited[i] = true;
                    count++;
				}
			}
		}
        
        System.out.println(count);
	}
}

아이디어를 떠올리는 것은 어렵지 않았지만, 접근을 잘못하였다.

• 시작점이 1로 되어야 한다.
• 컴퓨터 크기로 초기화하지 않고, 노드로 초기화하였다.