[백준 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번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

• 예제입력 1

  4
  1 3
  4 3
  4 2
  1 2

• 예제출력 1

  0 0 0 0

---

• 예제입력 2

  6
  1 2
  3 4
  6 4
  2 3
  1 3
  3 5

• 예제출력 2

  0 0 0 1 1 2

---

• 예제입력 3

  51
  1 2
  2 3
  3 4
  4 5
  5 6
  6 7
  7 8
  8 9
  9 10
  10 11
  11 12
  12 13
  13 14
  14 15
  15 16
  16 17
  17 18
  18 19
  19 20
  20 21
  21 22
  22 23
  23 24
  24 25
  25 26
  26 27
  27 28
  28 29
  29 30
  30 31
  31 32
  32 33
  33 34
  34 35
  35 36
  36 37
  37 38
  38 39
  39 40
  40 41
  41 42
  42 43
  43 1
  11 44
  44 45
  45 46
  46 47
  34 48
  48 49
  49 50
  50 51

• 예제출력 3

  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4

---

• 예제입력 4

  38
  1 2
  2 3
  3 4
  4 5
  5 6
  6 1
  1 7
  7 8
  8 9
  9 10
  10 11
  11 12
  12 13
  13 14
  14 15
  15 16
  16 17
  17 18
  18 19
  19 20
  20 21
  21 22
  22 23
  23 24
  24 25
  25 26
  26 27
  27 28
  28 29
  29 30
  30 31
  31 32
  32 33
  33 34
  34 35
  35 36
  36 37
  37 38

• 예제출력 4

  0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

---

• 예제입력 5

  12
  1 3
  3 4
  4 5
  5 6
  6 7
  7 8
  8 4
  2 3
  7 9
  9 12
  7 10
  10 11

• 예제출력 5

  2 2 1 0 0 0 0 0 1 1 2 2

---

정답

이 문제는 깊이우선탐색을 사용해서 순환선인 역을 찾아서 체크하는것이 포인트이다. 각 역은 깊이 우선탐색해 다시 자신으로 돌아오게 되면 그 역은 순환선에 속한 역임을 알수있고 순환선인 역을 체크해 놓은다음 각 역에서의 순환선 까지의 길이는 깊이탐색이나 너비탐색을 이용해 구할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;


public class Main {
    public static class Graph{
        boolean [] circle;
        LinkedList<Integer> subway[];
        public Graph(int n) {
            subway = new LinkedList[n+1];
            for(int i=0;i<n+1;i++) {
                subway[i] = new LinkedList<Integer>();
            }
            circle = new boolean[n+1];
        }

        public void print() {
            for(int i=0;i<circle.length;i++)
                System.out.print(circle[i]+" ");
        }

        //깊이탐색으로 순환선인지 지선인지 판단 순환선이면 cirle=true
        public void DFS(int station) {
            boolean [] visited = new boolean[subway.length+1];
            int length=0;
            DFSUtil(station,station,visited,length);
        }
        //깊이탐색
        public void DFSUtil(int start, int station,boolean [] visited,int length) {
            //먼저 들어온 위치 방문 체크
            visited[station] = true;
            length++;//한칸 늘었으니 ++

            //주변 역 가져옴
            Iterator<Integer> aroundstation = subway[station].listIterator();
            //주변역 재귀로 탐색
            //근데 주변역에 시작역 있으면 체크
            while(aroundstation.hasNext()) {
                int nextstation = aroundstation.next();
                //시작역이면
                if(nextstation == start && length>=3) {
                    circle[start] = true;
                    break;
                }
                if(!visited[nextstation]) {
                    DFSUtil(start,nextstation,visited,length);
                }
            }
        }

        //역 추가
        public void addEdge(String command) {
            String [] commands = command.split(" ");
            int a = Integer.parseInt(commands[0]);
            int b = Integer.parseInt(commands[1]);
            subway[a].add(b);
            subway[b].add(a);

        }
        //역 체크
        public void check(int station) {
            int length=0;
            boolean [] visited = new boolean[subway.length];
            checkUtil(station, length, visited);
        }
        public void checkUtil(int station, int length, boolean[] visited) {
            if(circle[station]) {
                System.out.print(length+" ");
                return;
            }
            visited[station] = true;
            Iterator<Integer> i = subway[station].listIterator();
            length++;
            while(i.hasNext()) {
                int nextstation = i.next();
                if(!visited[nextstation]) {
                    checkUtil(nextstation,length, visited);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        //그래프 생성
        Graph g = new Graph(n);
        ArrayList<String> section = new ArrayList<String>();
        for(int i=0;i<n;i++) {
            String command = br.readLine();
            section.add(command);
            g.addEdge(command);
        }
        //순환 역인지 지선인지 체크
        for(int i=1;i<=n;i++) {
            g.DFS(i);
        }
        //g.print();
        //역 거리 출력

        for(int i=1;i<n+1;i++) 
        { 
            g.check(i); 
        }



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