[BOJ24479] 알고리즘 수업 - 깊이 우선 탐색 1

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

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

문제

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

---

깊이 우선 탐색, DFS

깊이 우선 탐색은 한 루트로 계속 탐색해서 가장 깊이까지 들어간 후 다시 돌아가 다른 루트로 탐색하는 방식이다.

 

그림으로 간단하게 표현해서 보자.

시작점 부터 순서대로

가장 깊이까지 들어간 후 다시 돌아와 그 다음 지점에서 또 가장 깊이까지 들어가 탐색하는 것이다. 

 

문제에서 요구하는 것은 각 정점의 방문 순서이다.

'방문을 하는 순서'가 아니라 1-5-4-2-3 이라면 1-4-5-3-2 이렇게 출력 해야한다.

다음 조건들을 잘 만족시켜서 코드를 작성했다.

 

1. 양방향 간선

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int start = Integer.parseInt(st.nextToken());
    int to = Integer.parseInt(st.nextToken());
    //양방향 간선 체크
    graph.get(start).add(to);
    graph.get(to).add(start);
}

2. 오름차순 정렬

for(int i = 0; i < graph.size(); i++){
    Collections.sort(graph.get(i)); // 오름차순 정렬
}

❗️참고

ArrayList<ArrayList<Integer>>로 작성하면 예제 1번의 내부 구조는 다음과 같다.

[ [ ], [2, 4], [1, 3, 4], [2, 4], [1, 2, 3], [ ] ]

사실 ArrayList 사용하는 건 다른 분이 푼 걸 봤다.ㅎ 배열로 불면 메모리 초과가 뜬다고 하네용

 

네 번의 도전 끝에 성공! 

처음엔 반복문 크기를 잘못 지정해서 런타임 에러가 떴고, 그것만 틀린 줄 알고 바로 제출 했는데 74%? 까지 올라가다가 틀다는 문구가 떴다.. 맞힌 줄 알았는데 😭

 

정말 어디가 틀린건지 알 수 가 없었음.. 원래 visited랑 출력 배열을 따로 만들어서

visited는 정말 방문 여부만, 출력 배열에는 answer[vertex] = cnt;로 넣었는데 계속 틀렸다고하고 예제는 하나밖에 없고..

질문에 반례 찾아서 다 넣어봐도 다 맞는데 말이져....

 

너무 충격적이게도 뜻밖의 곳에서 찾았다..

함수 호출을 dfs(1)로 해줬던 것~ 🤯 dfs(R)로 고치고 나서 성공 받음..ㅎ

 

 

정답 코드는 아래 참고

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

public class BOJ24479 {
    private static int[] visited;
    private static int N, M, R, cnt = 1;
    private static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        visited = new int[N + 1];

        for(int i = 0; i < N+1; i++){
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            //양방향 간선 체크
            graph.get(start).add(to);
            graph.get(to).add(start);
        }

        for(int i = 0; i < graph.size(); i++){
            Collections.sort(graph.get(i)); // 오름차순 정렬
        }

        dfs(R);

        for(int i = 1; i < visited.length; i++){
            System.out.println(visited[i]);
        }
    }
    private static void dfs(int vertex) {
       visited[vertex] = cnt;

       for(int i = 0; i<graph.get(vertex).size(); i++) {
           int v = graph.get(vertex).get(i);
           if(visited[v] == 0) {
               cnt++;
               dfs(v);
           }
       }
    }
}