(Java) 백준 2606 - 바이러스

문제의 그래프를 보고 DFS / BFS를 이용하는 문제라고 생각했다.

먼저 DFS로 풀었는데 탐색경로 배열을 어떻게 해야 할지

잘 떠오르지 않아 한참을 고민했다.

탐색 경로 배열을 만들고 나니 DFS는 어렵지 않았다.

BFS는 이번에 처음 풀어봤는데 생각보다 재밌었다.

 

DFS는 깊이를 우선적으로 탐색해서 

BFS는 너비를 우선적으로 탐색한다고 알고는 있었지만

직접 몇 문제를 풀어보지 않아서 이해가 덜 갔던 것 같다.

 

그리 어렵지 않은 문제임에도 몇시간동안 입력값이 주어지면

어떤 흐름으로 가는지 생각하니 확실히 이해가 간다.

 

모든 정점을 탐색한다면 DFS와 BFS 모두 사용해도 괜찮을 것이고

그래프의 크기가 아주 크거나 경로의 특징이 들어있다면 DFS를 고려하고

최단거리 문제라면 BFS를 먼저 생각할 것 같다.

---

DFS 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int arr[][];
    static boolean visit[];
    static int n, r;
    static int answer;

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

        // 바이러스에 걸리는 컴퓨터 수
        answer = 0;
        // 탐색 경로 배열 (1부터 n까지 각각 연결된 노드배열)
        arr = new int[n + 1][n + 1];
        // 방문한 노드인지 확인
        visit = new boolean[n + 1];
        // 탐색 경로 배열
        for (int i = 0; i < r; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // 1-2 나 2-1 똑같음. 연결된 노드라면 1로 설정
            arr[a][b] = arr[b][a] = 1;
        }
        // dfs 실행
        dfs(1);
        System.out.println(answer);
    }

    public static void dfs(int i) {
        visit[i] = true;
        for (int j = 1; j < n + 1; j++) {
            // 연결된 노드를 발견하고 방문한적이 없다면
            if(arr[i][j] == 1 && visit[j] == false) {
                // answer를 증가시키고 재귀를 통해 depth 증가
                answer++;
                dfs(j);
            }
        }
    }
}

 

BFS 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int arr[][];
    static boolean visit[];
    static int n, r;
    static int answer;

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

        answer = 0;
        arr = new int[n + 1][n + 1];
        visit = new boolean[n + 1];

        for (int i = 0; i < r; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr[a][b] = arr[b][a] = 1;
        }
        bfs(1);
        System.out.println(answer);
    }

    public static void bfs(int i) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i);
        visit[i] = true;
        // 큐가 비어 있다는것은 순회가 끝났다는것
        while (!queue.isEmpty()) {
            // i번부터 탐색
            int temp = queue.poll();
            for (int j = 1; j < n + 1; j++) {
                // 노드가 연결되어 있고 방문하지 않았다면
                if (arr[temp][j] == 1 && visit[j] == false) {
                    // 방문처리하고 큐에 넣기
                    visit[j] = true;
                    queue.offer(j);
                    answer++;
                }
            }
        }
    }
}