[백준] 2606 바이러스 | 그래프, DFS, BFS | 실버 Ⅲ | JAVA 💡DFS

📌 문제

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

 

⭐ DFS(깊이 우선 탐색)란?

DFS는 그래프의 탐색 방법 중 하나로, 한 노드를 방문한 후 그 노드와 연결된 노드를 깊이 있게 탐색하는 방식입니다.

즉, 현재 노드에서 갈 수 있는 경로를 따라 최대한 깊이 들어간 후, 더 이상 갈 수 없게 되면 다시 돌아와서 다른 경로를 탐색하는 방식입니다.

이 방법은 재귀를 통해 구현할 수 있으며, 그래프의 연결 구조를 탐색하는 데 매우 유용합니다.

 

⭐ 전체 코드

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

public class Main{
    
    static boolean[][] a;
    static int n;
    static boolean[] b;
    static int count = 0;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        int e = Integer.parseInt(br.readLine());
        
        a = new boolean[n+1][n+1];
        b = new boolean[n+1];
        
        for (int i = 1; i<=e; i++){
            st = new StringTokenizer(br.readLine());
            int aa  = Integer.parseInt(st.nextToken());
            int bb = Integer.parseInt(st.nextToken());
            a[aa][bb] = a[bb][aa] = true;
        }
        
        b[1]=true;
        
        dfs(1);
        
        System.out.println(count-1);
    }
    public static void dfs(int node){
        count++;
        b[node]=true;
        
        for (int i=1; i<=n; i++){
            if (a[node][i]==true && b[i]!=true){
                dfs(i);
            }
            
        }
    }
}

 

⭐ 코드 분석

✅ 2차원 배열 사용

static boolean[][] a;

a = new boolean[n+1][n+1];

이 문제에서 2차원 배열을 사용하는 이유는 각 컴퓨터 간의 연결 관계를 직관적으로 표현하기 위함입니다.

사실 맨 처음에는 2차원 배열의 행, 열을 둘 다 노드의 개수로 하지 않고, 행은 노드의 개수, 열은 엣지의 개수로 했는데요..?(노답) 이러니까 탐색을 하려고 할 때 답이 없더라구요.ㅎ (당연함.) 

행과 열을 모두 노드의 개수로 해야 연결 관계를 직관적으로 확인할 수 있습니다!

사람은 연결 관계를 화살표로 표현할 수 있지만, 컴퓨터에는 이런 시각적 요소가 없기 때문에 이를 표현하는 방법을 생각해내기가 좀 어려웠습니다.

이 글을 쓰다보니 N 사고가 폭발해서 더보기 글로 씁니다^^

 

어떻게 보면 컴퓨터랑 인간은 다른 차원의 존재, 외계인과 인간 같다는 생각이 들었다. 그래서 서로를 이해를 못함. like 컨택트
오해의 요지 없이 정확히 의사표현을 하기 위해 이렇게 노력해야한다는 것을 몸소 느꼈다. 
또다른 예시로는 자신과 생각이 너무나 다른 사람을 이해시키기 위해서는 왜 이걸 이해못해?라는 마인드가 아닌, 이해시키기 위해 내 생각을 이 사람에게 이해시키기 위해 최선을 다해 표현해야한다고 느꼈다.

아무튼 현실판 컨택트(영화)가 벌어진다면, 언어학자만 부르지말고 나도 불러줬으면 좋겠다.

컴퓨터와 대화하는 사람인데요?

언어학자는 사람이랑만 대화하는 거 아니냐며~

2차원 배열을 사용하여 행과 열 모두 노드를 나타내고, 해당 인덱스의 값이 1이면 그 인덱스를 이루고 있는 행과 열, 두 노드가 연결되어 있다는 것을 표현할 수 있습니다.

for (int i = 1; i<=e; i++){
            st = new StringTokenizer(br.readLine());
            int aa  = Integer.parseInt(st.nextToken());
            int bb = Integer.parseInt(st.nextToken());
            a[aa][bb] = a[bb][aa] = true;
        }

이렇게 함으로써, 그래프의 구조를 명확하게 나타낼 수 있으며, 복잡한 연결 관계를 코드로 쉽게 처리할 수 있습니다.

✅ DFS 구현 방법

public static void dfs(int node){
        count++;
        b[node]=true;
        
        for (int i=1; i<=n; i++){
            if (a[node][i]==true && b[i]!=true){
                dfs(i);
            }
            
        }
    }

사실 처음에는 모든 노드가 dfs 메서드를 거친다고 생각해서 if문 안에서 방문 표시를 하고 main 함수 내에서 for문을 통해 방문 배열을 탐색해서 1이 있으면 count했었는데요.

생각해보니 dfs 메서드가 호출됐다는건, 해당 node가 1과 연결된(혹은 연결된 노드에 연결된) 노드이기 때문에 별도로  for문을 통해 방문 배열을 탐색할 필요 없이 dfs 메서드 내에 들어오자마자 count하면 되고, 방문 배열에 표시하면 됐습니다.

즉, dfs 메서드 자체가 방문했을 때 호출되는 메서드고, dfs 내의 for문, if문은 연결됐는지 안 됐는지를 판가름하는 곳이 아닌 연결된 노드를 탐색하기 위함이었던 거죠! 

재귀 호출은 현재 노드에서 다음 노드로 이동하며, 이 과정을 반복합니다. 이렇게 깊이 있는 탐색을 통해 연결된 모든 컴퓨터를 방문하게 됩니다.

이와 같이 DFS는 재귀적 방법으로 연결된 노드를 깊이 있게 탐색하여, 그래프 구조에서 특정 조건을 만족하는 노드를 찾는 데 유용한 알고리즘입니다. 

 

⭐ DFS 알고리즘을 사용해야 할 때

• 그래프 구조(노드와 노드 간 연결 관계)
  • 네크워크, 소셜 네트워크
  • 연결된 노드 탐색 등
• 경로 탐색
  • 특정 시작점에서 도착점까지의 경로
• 특정 조건을 만족하는 모든 경우의 수를 찾는 문제 (예: 조합, 순열 등)
• 백트래킹
  • 퍼즐, 미로 찾기

---

 

int 배열을 boolean 배열로 바꿨을 때 메모리 감소, 방문 배열 for문으로 count 하지 않고 dfs 메서드 내에서 count 해도 메모리 감소 X

 

---

 

고뇌의 흔적