그래프 - 백준 2606 - 바이러스 - JAVA - DFS구현 방법

그래프 유형으로 들어왔다. 그래프에서 중요한 것은 각 문제별로 어떤 특징을 가진 그래프인지 알고 해당 그래프의 특성에 맞게 잘 자료구조로 나타낸다음? 문제에서 원하는 답을 도출할 수 있도록 순회를 해서 답을 내는 것

문제 푸는 법

• 원하는 답이 뭔지를 보자 -> 바이러스에 걸리게 되는 컴퓨터의 수를 구하라는 것 -> 그래프에서 1번 노드와 연결되어있는 노드의 수를 세면 된다.
• 단순히 연결되어있는 애들을 보는 것이기 때문에 순회 방법은 크게 상관이 없다. -> 어려운 문제에선 상관이 있겠구나라는것만 인지하자
• 단순한 문제이기 때문에 그래프를 인접행렬로 구현할지 인접리스트로 구현할지는 상관이 없다. -> 어려운 문제에선 상관이 있겠구나라는것을 인지하자 
• 그래프는 무방향 그래프이구나 라는 것만 챙겨가면 되겠다. -> 그래프의 종류들이 달라질 수 있구나라는 것을 인지하자

코드

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

public class Main {
    static int n;
    static int[] visited;
    static int[][] graph;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());
        visited = new int[n + 1];
        graph = new int[n + 1][n + 1];

        int m = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < m; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        dfs(1);
        System.out.println(ans-1);
    }

    static void dfs(int node) {
        if (visited[node] == 1) {
            return;
        }
        visited[node] = 1;
        ans++;

        for (int i = 1; i < n + 1; i++) {
            if (visited[i] == 0 && graph[node][i] == 1) {
                dfs(i);
            }
        }
    }
}

해설

• 컴퓨터의 개수는 n개 -> node 의 개수가 n개
  • 내가 어떤 노드를 방문했나 안했나에 대한 정보를 가지고있을 visited라는 배열의 길이를 node 개수 +1 로 만들어준다.
    -> 우리가 도는 index와 맞춰주면 편하니까 +1 로 해주는것
• 그래프는 인접 행렬로 구현 graph[1][2] 나 graph[2][1] 의 값이 1이면 1번노드와 2번노드는 연결되어 있다는 정보를 가진 자료구조가 되는 것
• dfs는 재귀로 구현을 했고 1번 노드에서 시작은 고정된 값
• 1번 노드는 계산에서 빼기때문에 마지막에 answer에서 1을 뺀 값을 출력

 

갈수록 어려운 문제로 가보장