[코테] 백준 2606 바이러스: DFS Java

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

 

DFS로도 풀 수 있고 BFS로도 풀 수 있는 문제다.

난 DFS로 풀었다.

 

두가지 부분을 나눠 보면 된다.

1) 값을 입력 받는 부분

2) dfs 함수 부분

 

1) 값 입력 부분

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

        int num = Integer.parseInt(br.readLine()); // 컴퓨터 수
        int connections = Integer.parseInt(br.readLine()); // 연결 수

        visited = new boolean[num + 1];
        computers = new ArrayList[num + 1];

        for (int i = 1; i <= num; i++) {
            computers[i] = new ArrayList<>();
        }

        for (int i = 0; i < connections; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            computers[a].add(b);
            computers[b].add(a); // 양방향 연결
        }

        dfs(1); // 1번 컴퓨터에서 시작
        System.out.println(count - 1); // 1번 컴퓨터는 제외하고 출력

        br.close();
    }

computers와 visited 변수만 알면 된다.

computers는 ArrayList 배열이다. List[] 타입.

각 컴퓨터에 연결된 컴퓨터 ArrayList를 담는다고 생각하면 된다.

우선 첫 번째 for문에서 각 배열에 ArrayList로 초기화 해주고,

두 번째 for문에서 '연결되어 있는 컴퓨터 정보 인풋'를 통하여, 각각 배열 ArrayList에 연결되어있는 컴퓨터를 담는다.

만약 1 2가 들어온다면

computers[1] 에 {2}가 담기는 식이다.

computers[2]에는 {1}이 담길 것이다.

 

2) dfs 함수 부분

private static void dfs(int node) {
    if (visited[node]) {
        return;
    }

    visited[node] = true;
    count++;

    for (int neighbor : computers[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

만약 이미 방문한 컴퓨터라면 dfs 함수를 끝낸다.

그게 아니라면 true로 바꾸고 count를 올린다.

for문으로 computers[node] 즉, node번 컴퓨터와 연결되어 있는 컴퓨터를 순회한다.

 

1번 컴퓨터에 {2,3}이 직접 연결되었다고 치고

2번 컴퓨터에는 {5}

5번 컴퓨터에는 {4}가 있다고 치자.

 

처음 node는 1이다. 1번 컴퓨터와 연결된 2번으로 dfs를 타고, 2번 컴퓨터에 연결되어 있는 5번으로, 4번으로 총 3depth가 들어간다. (count는 4가 된다. - node 1 포함)

그리고 dfs 함수에 차례대로 탈출해 node는 다시 1이 되고, 1번 컴퓨터와 연결된 3번으로 dfs를 탄다. 3번과 연결된 컴퓨터는 없기 때문에 for문을 타지 않고 그대로 탈출. count는 총 5가 된다.

 

처음 입력 구조를 잡는 게 어려운 것 같다....

 

총 코드

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

public class baekjoon_2606 {

    static int count;
    static boolean[] visited;
    static List<Integer>[] computers;

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

        int num = Integer.parseInt(br.readLine()); // 컴퓨터 수
        int connections = Integer.parseInt(br.readLine()); // 연결 수

        visited = new boolean[num + 1];
        computers = new ArrayList[num + 1];

        for (int i = 1; i <= num; i++) {
            computers[i] = new ArrayList<>();
        }

        for (int i = 0; i < connections; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            computers[a].add(b);
            computers[b].add(a); // 양방향 연결
        }

        dfs(1); // 1번 컴퓨터에서 시작
        System.out.println(count - 1); // 1번 컴퓨터는 제외하고 출력

        br.close();
    }

    private static void dfs(int node) {
        if (visited[node]) {
            return;
        }

        visited[node] = true;
        count++;

        for (int neighbor : computers[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
}