[실버 3] [Java] 백준 2606번: 바이러스

아이디어

오늘은 그래프 문제를 처음 풀어봤다. 자바에서 그래프를 어떻게 만드는지, 어떻게 탐색하는지 몰라서

GPT에게 기본적인 그래프 문제의 코드를 보여달라 하고 공부한 후 문제를 풀었는데

너무 기본적인 그래프 문제였던지 그 코드와 완전 같은 방식으로 풀리는 문제였다.

main 메서드와 dfs, bfs에서 visited[]와 graph를 모두 사용하고, 변경된 결과가 반영되야 하므로 두 자료형은 전역변수로 선언하고

그래프의 크기는 N+1 (node의 번호를 0부터 셌으므로)

visited의 크기도 N+1로 하였고

초기화 해준 다음 연결된 컴퓨터의 쌍의 수만큼 반복하여 그래프의 간선을 추가해주었다.

이 그래프의 경우 양방향이므로 graph.get(node).add(neighbor)와 graph.get(neighbor).add(node)를

둘 다 해줘야 한다. 깜빡하고 하나만 해서 틀렸다...

 

dfs는 재귀함수의 형태이고, 먼저 visitied[node]를 true로 한다.

그 후 for (int next : graph.get(node))를 한다.

graph.get(node)는 node에 인접한 node의 리스트를 반환하는데, 그 리스트들이 visitied가 아니면

다시 dfs를 하여 해당 가지부터 반복해서 탐색하고, 해당 방향의 가지가 모두 탐색이 끝나면 다른 방향으로 깊이 들어가는 구조이다.

이렇게 하면

dfs(1) -> node = 1, visited[1] = true

graph.get(node) = [2, 5]

  next = 2, dfs(2) -> node = 2, visited[2] = true

  graph.get(node) = [3]

    next = 3, dfs(3) -> node = 3, visited[3] = true

    graph.get(node) = []

  next = 5, dfs(5) -> node = 5, visited[5] = true

  graph.get(node) = [6]

    next = 6, dfs(6) -> node = 6, visited[6] = true

    graph.get(node) = []

 

위와 같은 과정으로 탐색을 진행한다.

 

bfs는 queue를 이용하고, queue를 선언한 후 q.add()를 하여 첫 node를 추가해준다.

그 후 해당 node를 vistied하고 queue가 모두 빌 때까지 반복하도록 while을 씌운다.

그 후 node = q.poll()를 하여 탐색할 node를 설정하고

for (int next : graph.get(node))를 씌운다.

만약 next가 visited가 아니면 true로 바꾸고, q.add(next)를 한다.

이렇게 하면 start가 1일 때

queue에 1 추가, visited[1] = true

queue에서 1 추출, node = 1

graph.get(node) = [2, 5], queue에 2, 5 추가, visited[2] = visited[5] = true, 현재 queue에 2, 5 있음

queue에서 2 추출, node = 2

graph.get(node) = [3], queue에 3 추가, visited[3] = true, 현재 queue에 5, 3 있음

queue에서 5 추출, node = 5

graph.get(node) = [6], queue에 6 추가, visited[6] = true, 현재 queue에 3, 6 있음

queue에서 3 추출, node = 3

graph.get(node) = [], queue에 6 있음

queue에서 6 추출, node = 6

graph.get(node) = [], queue 비어있음, while문 종료

 

위와 같은 과정으로 탐색을 진행한다.

 

이를 코드로 구현하면 다음과 같다.

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

public class N2606 {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;
    
    public static void dfs (int node) {
        visited[node] = true;

        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    public static void bfs (int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int L = Integer.parseInt(br.readLine());
        
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < L; i++) {
            String[] input = br.readLine().split(" ");
            int node =  Integer.parseInt(input[0]);
            int neighbor = Integer.parseInt(input[1]);
            graph.get(node).add(neighbor);
            graph.get(neighbor).add(node);
        }

        visited = new boolean[N+1];
        dfs(1);

        int count = -1;
        for (boolean b : visited) {
            if (b) {
                count++;
            }
        }
        System.out.println(count);
    }
}

 

---

아직 초보라 많이 서툴고 틀린 부분이 있을 수 있습니다. 고수분들께서 조언해주실만한 사항이 있으면 감사히 받겠습니다.