[백준] 16947번 : 서울 지하철 2호선

16947번: 서울 지하철 2호선

---

[DFS + BFS]

DFS로 순환을 찾아내고, 찾아낸 사이클에 포함된 정점들에서 BFS를 수행해 사이클이 아닌 정점들까지의 거리를 구한다.

 

처음에 이 DFS로 사이클을 찾아내는 방법을 잘 모르겠어서, 방문한 정점을 문자열에 담아 사이클을 찾으면 그것을 따로 저장하는 식으로 해서 문제를 풀었었는데, 어디가 틀린지 도저히 못찾겠어서 패스하고 다시 풀었다.

 

하지만 이번에도 어렵게 느껴져서 결국 다른 분의 코드를 참고해서 풀었다.

참고: kyu9341.github.io

 

이분은 정점에 대해 방문/방문X, 사이클 발견/사이클 미발견의 경우를 나누어 접근하신 것 같다.

자세한 설명은 내가 하기보다 위 블로그를 보는 것이 더 자세하게 나와있다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static List<Integer>[] list = new ArrayList[3001];
    static int[] visit = new int[3001], dist = new int[3001];
/*
visit
0 : 방문하지 않음
1 : 방문, 사이클 X
2 : 방문, 사이클 O
*/
static int DFS(int x, int before){
/*
DFS
-1 : 사이클을 못 찾음
-2 : 사이클을 찾음 but, 사이클에 포함 X
1 ~ n : 사이클을 찾음, 사이클에 포함 O
결과적으로 visit는 0, 1, 2중 하나를 갖게 된다. 이때 0과 1은 중요치 않고 2가 중요하다.
찾은 사이클에서 BFS를 실행해 지선으로 뻗어나갈 것 이기 때문
*/
    if(visit[x] == 1)
        return x;

    visit[x] = 1;

    for(int next:list[x]){

        if(next == before) continue;

        int result = DFS(next, x);

        if(result == -2) return -2;
        if(result > 0){
            visit[x] = 2;
            if(x == result) return -2;
            else return result;
        }
    }
    return -1;
}

    static boolean[] check = new boolean[3001];
    static void BFS(int x){

        Queue<Integer> Q = new LinkedList<>();

        check[x] = true;
        Q.add(x);

        while(!Q.isEmpty()){
            int cur = Q.poll();

            for(int next:list[cur])
                if(visit[next] != 2 && !check[next]){

                    check[next] = true;
                    dist[next] = dist[cur] + 1;
                    Q.add(next);
                }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int home = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            list[home].add(target);
            list[target].add(home);
        }

        DFS(1, 0);

        for(int i=1; i<=n; i++)
            if(visit[i] == 2)
                BFS(i);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++)
            sb.append(dist[i]).append(' ');

        System.out.println(sb);
    }
}