[Java] baekjoon_2606 : 바이러스

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

바이러스 : Silver3

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

2606번: 바이러스

 

풀이

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  static ArrayList<Integer>[] graph;
  static boolean[] visited;

  public static void main(String[] args) throws IOException {
    int computers = Integer.parseInt(br.readLine()); // 컴퓨터 개수
    int N = Integer.parseInt(br.readLine()); // 연결 컴퓨터 쌍의 개수

    // 그래프를 인접 리스트로 구현
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    for (int i = 0; i <= computers; i++) {
      graph.add(new ArrayList<>());
    }

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int from = Integer.parseInt(st.nextToken());
      int to = Integer.parseInt(st.nextToken());
      graph.get(from).add(to);
      graph.get(to).add(from);
    }

    int cnt = bfs(graph, computers);
    bw.write(cnt + "\n");

    br.close();
    bw.close();
  }

  public static int bfs(ArrayList<ArrayList<Integer>> graph, int computers) {
    boolean[] visited = new boolean[computers + 1];
    Queue<Integer> queue = new LinkedList<>();
    int cnt = 0; // 웜 바이러스에 걸린 컴퓨터 수

    queue.offer(1); // 1번 컴퓨터부터 시작
    visited[1] = true;

    while (!queue.isEmpty()) {
      int current = queue.poll();
      cnt++;

      // 현재 컴퓨터와 연결된 컴퓨터들 중 방문하지 않은 컴퓨터를 큐에 추가
      for (int next : graph.get(current)) {
        if (!visited[next]) {
          visited[next] = true;
          queue.offer(next);
        }
      }
    }
    return cnt - 1;
  }
}

 

ㄴ 그래프를 표현하기 위해 인접 리스트로 구현된 ArrayList<ArrayList<Integer>> graph를 생성했다.

    ㄴ 이중 ArrayList를 사용하여 각 컴퓨터의 연결 정보를 저장한다.
ㄴ 그래프의 초기화를 위해 모든 컴퓨터에 대한 ArrayList를 생성한다.
ㄴ 연결된 컴퓨터 쌍의 개수만큼 반복하면서 입력으로 주어진 연결 정보를 그래프에 추가한다.
ㄴ BFS 메서드를 호출하여 웜 바이러스에 걸린 컴퓨터의 수를 계산하고 결과를 출력한다.

    ㄴ visited 배열을 사용하여 각 컴퓨터의 방문 여부를 관리한다.
    ㄴ 시작점으로 지정한 1번 컴퓨터를 큐에 추가하고 방문 여부를 체크한다.
    ㄴ 큐가 빌 때까지 아래 과정을 반복합니다.
    ㄴ 큐에서 컴퓨터를 하나 꺼내서 현재 컴퓨터로 지정한다.
    ㄴ 현재 컴퓨터와 연결된 컴퓨터들 중 아직 방문하지 않은 컴퓨터를 큐에 추가하고 방문 여부를 체크한다.
    ㄴ BFS 탐색이 완료되면 웜 바이러스에 걸린 컴퓨터의 수를 반환한다.