[백준 *Java] - 서울 지하철 2호선

서울 지하철 2호선

16947번: 서울 지하철 2호선

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

---

 

👇  내 접근 방식 (내 생각 정리)

처음에 해당 문제를 이해하는 데 오래 걸렸습니다. 일단 문제로만을 보고 로직 설계를 할 수가 없었고,

테스트케이스를 통해서 문제를 이해하는 방식으로 바꾸었습니다. ( * 테스트케이스로 되도록 문제를 이해하는 습관을 들이지 말자 )

 

테스트케이스를 가지고 해당 문제를 이해한대로 설명하자면,

노드의 갯수(지하철 역)이 정해지고 

각 노드의 인접한 노드 정보를 입력값으로 줍니다.

그리고 전체 노드를 간선으로 이었을 시, 순환이되는 노드들 뭉치가 있을 거고, 순환이 안되고 위 지하철 그림에서 보는 바와 같이 지선으로 빠진 부분이 있을 겁니다.

 

순환선과 지선에 있는 노드들을 찾은 뒤,

순환선에 있는 역(노드)들은 거리가 0이 될 것이고,

지선에 있는  역(노드)들은 순환선에서 벗어나온 거리만큼을 세주어야 합니다.

 

여기서 정리를 하면,

순환으로 이루어진 노드 뭉치는 무조건 하나가 존재할 것입니다.

그리고, 문제를 구현하기 위해서는 순환선에 있는 역들과 지선에 있는 역들이 무엇인지 나누고 시작을 해야합니다.

그래야, 거리를 잴수가 있습니다.

 

 

아래 코드에 주석을 통해 코드 설명을 넣어 놓았습니다.

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

public class Boj_16947 {

    static int N;
    static ArrayList<ArrayList<Integer>> adjArr = new ArrayList<>();
    static int[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        /*
            check 배열
                순환선에 속하지 않는 역은 '0' 저장
                순환선에 속한 역은 시작점에서 '해당 역까지 가는데 소요된 비용' 저장
         */
        check = new int[N + 1];

        // 지하철 노선 선언
        for(int i = 0; i < N + 1; i++){
            adjArr.add(new ArrayList<>());
        }

        // 지하철 노선 초기화
        for(int i = 1; i < N + 1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            adjArr.get(x).add(y);
            adjArr.get(y).add(x);
        }

        // 순환선 탐색 (사이클)
        dfs(1, -1, 1);


        int[] distance = new int[N + 1]; // 순환점에서 지선 역(노드)의 거리를 구하여 담습니다.

        for (int i = 1; i < N + 1; i++) {
            // 지선만을 in 하게끔, 노드의 인접 노드가 2개를 초과하게되면 순환이 아니다.
            if(adjArr.get(i).size() > 2 && check[i] != 0){
                Queue<Integer> qu = new LinkedList<>();
                qu.offer(i);
                while (!qu.isEmpty()) {
                    int node = qu.remove();

                    for (int adjNode : adjArr.get(node)) {
                        // 순환선 포함 역 또는 이미 방문한 지선 역은 pass
                        if (check[adjNode] != 0 || distance[adjNode] != 0) continue;

                        qu.offer(adjNode);
                        distance[adjNode] = distance[node] + 1; // 떨어진 정도 저장
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < N + 1; i++){
            sb.append(distance[i]).append(' ');
        }

        System.out.println(sb);
    }

    public static boolean dfs(int node, int beforeNode, int cnt) {
        // base case
        /*
            사이클(순환선) 발견 시 true 로 리턴
            그리고, 이 떄 사이클은 발견했으니, 사이클에 포함되지 않는 부분은 0으로 채움.
            why? 현재 node 가 순환점의 시작점이다.
         */
        if(check[node] != 0) {
            for (int i = 1; i < N + 1; i++) {
                if(check[i] < check[node]) check[i] = 0;
            }
            return true;
        }

        // dfs 탐색
        for(int adjNode : adjArr.get(node)) {
            if(adjNode == beforeNode) continue; // 직전에 방문한 역은 방문x

            // dfs 재귀 루프 구현 부분
            check[node] = cnt;
            if(dfs(adjNode, node, cnt+1)) return true;
            check[node] = 0;

        }
        return false;
    }
}