백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 - JAVA

24479 문제링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int count;
    static int[] checked;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        
        checked = new int[n+1];
        
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            
            graph.get(u).add(v);
            graph.get(v).add(u);
        } 
        
        for(int i = 1; i <= n; i++) {
            Collections.sort(graph.get(i));
        }
        
        count = 1;
        dfs(r);
        for(int i = 1; i <= n; i++) {
            sb.append(checked[i]).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }
    
    private static void dfs(int node) {
        checked[node] = count;
        for(int i = 0; i < graph.get(node).size(); i++) {
            int newNode = graph.get(node).get(i);
            if(checked[newNode] == 0) {
                count++;
                dfs(newNode);
            }
        }
    }
}

 

알고리즘 설명

---

DFS(Depth First Search) 알고리즘에 대해 알고있다면 쉽게 풀 수 있는 문제라고 생각합니다.
DFS는 트리구조나 그래프에서 사용되는 탐색 알고리즘입니다. 깊이를 우선으로 탐색하고 없으면, 이전 단계로 돌아가서 다른 경로를 탐색하는 방식으로 동작합니다.
해당 문제에서는 노드들의 연결이 아래 그림과 같이 연결되어 있습니다.

문제에서 인접 접점은 오름차순으로 방문한다고 했으므로, 숫자가 낮은 노드부터 차례대로 방문하게 됩니다.
따라서, 루트 노드가 1인 경우, DFS 탐색 순서는 1 → 2 → 3 → 4 입니다.
DFS는 노드의 Depth를 기준으로 내려가며 방문하는 형식이기때문에, 스택형식으로 함수를 쌓아가는 재귀함수를 활용하여야 하고, 더 이상 내려갈 노드가 없을 때, 함수를 종료하는 방식의 접근이 필요합니다.
 
 

고민했던 부분

---

문제에서도, 방문 순서를 출력하라고 했기 때문에, 크기가 정해져있는 2차원 배열로 만들어야 하는지, 2차원 ArrayList를 써서 빠르게 순서를 찾아야 할지 고민했었습니다.
노드의 입력범위는 10만, 간선의 입력범위는 20만까지였기 때문에, 2중 배열로 만들 경우에는 각 배열들의 길이의 크기가 고정이므로, 연결되지 않는 간선까지 저장된다는 사실을 생각할 수 있었습니다. 하지만 시간과 공간 복잡도에 대한 정확한 기준을 계산할 필요가 있었습니다.
N은 노드의 수, M은 간선의 수입니다.
 

1. 2차원 배열의 공간복잡도 / 시간복잡도
   2차원 배열은 모든 노드와의 관계가 표현되어야 하기 때문에, 노드의 갯수가 N개일 경우 arr[N][N]입니다. 따라서 총 원소의 갯수는 N * N개가 들어갈 수 있습니다. 따라서 2차원 배열의 크기는 N * N 입니다. → 공간복잡도 : O(N²)
   특정 노드간의 연결을 탐색하려면 배열의 크기와 상관없이 바로 탐색할 수 있으므로 O(1)입니다. 하지만 모든 노드의 간선의 갯수(두 개의 노드가 연결되있는지)를 확인하려면 배열의 크기만큼 반복해야하므로, N * N 입니다. → 시간복잡도 : O(N²)
2. 2차원 ArrayList의 공간복잡도 / 시간복잡도
   2차원 ArrayList는 각 노드마다 연결된 다른 노드들만 저장하는 방식입니다. 따라서 각 ArrayList에 저장된 노드들의 갯수가 해당 노드의 간선의 갯수입니다. 노드의 갯수만큼 리스트를 생성하므로 O(N), 각 리스트에서 연결된 노드들을 추가하므로 O(M) 입니다.
   따라서 O(N)과 O(M)을 더한것이 2차원 ArrayList의 크기입니다. → 공간복잡도 : O(N + M)
   2차원 ArrayList에서 두 노드가 연결되어있는지 확인하려면, 해당 노드의 리스트를 순차적으로 탐색해야하므로 O(M)입니다. 모든 노드의 간선을 확인하려면 N개의 노드를 전부 M만큼 탐색해야하므로, O(M)을 O(N)만큼 반복해야 합니다. → 공간복잡도 : O(N + M)

결론: 간선이 많고 노드수가 상대적으로 적을 때는 2차원 배열이 효율적이고, 노드의 갯수가 많아질수록, 낭비되는 메모리를 줄이기 위해서, 2차원 ArrayList가 효율적입니다.
 

 
- 참고 -

• O(1)은 상수시간으로, 연산시간이 입력의 크기와 관계없이 일정한 경우를 나타냅니다.

 

코드 해석

---

2차원 ArrayList를 생성하고, 각 노드에 연결된 노드들을 추가합니다. 각 리스트들을 오름차순으로 정렬하고, dfs함수를 생성해서 노드 r을 checked 배열 첫번째에 삽입하고, 노드 r을 기준으로 연결된 노드들이 checked 배열에 있는지 확인한 후 있으면 종료하고, 없으면 dfs를 재귀호출합니다.