99클럽 코테 스터디 Java 4일차 TIL - 알고리즘 수업 - 깊이 우선 탐색 1 : 백준 24479번 - DFS

1. 오늘의 문제 - 알고리즘 수업 - 깊이 우선 탐색 1 - 백준 24479번

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

 

1년 전에 풀었던 문제가 나왔네?

다시 한 번 풀어보자.

다시 풀어봤는데, 첫 번째, 두 번째 제출은 틀렸고, 세 번째 만에 맞췄다.

2. 문제 풀이 전략

2 - 1. 인접리스트로 접근

일단 정점수가 100,000이다.

인접행렬로 풀 경우, 100,000 * 100,000 이니까 공간 복잡도가 어마어마해진다.

정점수가 적을 때는 인접행렬로 풀어도 되지만, 이런 경우 인접리스트로 풀어야 시간초과가 안 난다.

static List<List<Integer>> adjList;

2 - 2. 정렬

예시의 입력을 살펴보면, 1과 4가 연결, 1과 2가 연결순으로 제시된다.

1번과 연결된 놈들이  [4, 2] 가 되는 것이다.

문제에서 요구한 것이 "오름차순"이므로 정렬 해준다.

 

2 - 3. 양방향 그래프 체크해주기

이거 안해주고 제출해서 첫 번째 제출이 틀려버렸다.

양방향 이므로, 1번 정점이 4번 정점과 연결, 4번 정점이 1번 정점과 연결 됨을 나타내줘야 한다.

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    adjList.get(a).add(b);
    adjList.get(b).add(a);  // 양방향 그래프!
}

 

2 - 4. 방문 순서 추적 변수 사용하기

이것도 안해줘서 두 번째 제출이 틀려버렸다.

처음에는 방문순서를 기록해주는 로직을 아래 처럼 작성했다.

 

static void dfs(int node) {
    for (int x : adjList.get(node)) {
        if (ch[x] == 0) {
            ch[x] = ch[node] + 1;  // 이렇게!
            dfs(x);
        }
    }
}

 

현재 정점(node) 에서 방문하려는 정점(x)에 갈 때 node 방문순서 + 1을 해주면 될 거라 생각했다.

제시된 예제에서는 가능했다.

이게 안 되는 이유는 아래 같은 상황이다.

나와야 하는 방문 순서는 ch = [0, 1, 2, 3, 4] 이거인데

내 로직은 ch = [0, 1, 2, 3, 2] 가 된다. 

따라서, 방문 순서 추적 변수를 사용해야 한다.

 

3. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

// 4. 알고리즘 수업 - 깊이 우선 탐색 1 - 백준 : 24479
public class Dfs4 {

    static int N;
    static int M;
    static int start;
    static List<List<Integer>> adjList;
    static int[] ch;
    static int order = 1;

    static void dfs(int node) {
        for (int x : adjList.get(node)) {
            if (ch[x] == 0) {
                ch[x] = ++order;
                dfs(x);
            }
        }
    }

    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());
        N = Integer.parseInt(st.nextToken()); // 정점의 수
        M = Integer.parseInt(st.nextToken()); // 간선의 수
        start = Integer.parseInt(st.nextToken()); // 시작 정점

        adjList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adjList.get(a).add(b);
            adjList.get(b).add(a);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(adjList.get(i));
        }

        ch = new int[N + 1];
        ch[start] = order;
        dfs(start);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(ch[i]).append("\n");
        }

        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }
}

 

4. 소감

드디어 DFS 문제가 나왔다.

근데, 1년 전에 풀었던 문제인데도 바로 못 마추네.

그래도 풀긴 해서 뿌듯하다. 

남는 게 있구나.