[BaekJoon] 16947 서울 지하철 2호선 (Java)

1.  문제 링크

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

2.  문제

요약

• 지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개가 있습니다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있습니다.
• 2호선은 순환선 1개와 2개의 지선으로 이루어져 있습니다.
• 한 역에서 출발해 다시 출발한 역으로 돌아올 수 있는 순환선이라고 한다.
• 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
• 두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수입니다.
• 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값입니다.
• 지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 3,000보다 작거나 같은 역의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 역과 역을 연결하는 구간의 정보가 주어집니다. 같은 구간이 여러 번 주어지는 경우는 없고 역은 1번부터 N번까지 번호가 매겨져 있습니다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어집니다.
• 출력: 총 N개의 정수를 출력합니다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 출력합니다.

3.  소스코드

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

public class Main {
    static int N;
    static HashMap<Integer, ArrayList<Integer>> map;
    static HashSet<Integer> loopLine = null;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        map = new HashMap<>();
        for(int station = 1; station <= N; station++)
            map.put(station, new ArrayList<>());

        for(int path = 0; path < N; path++) {
            int station1 = scanner.nextInt(), station2 = scanner.nextInt();

            map.get(station1).add(station2);
            map.get(station2).add(station1);
        }
    }

    static void solution() {
        StringBuilder sb = new StringBuilder();

        for(int station = 1; station <= N; station++) {
            boolean[] visited = new boolean[N + 1];
            getLoopLineStations(station, -1, station, visited, new ArrayList<>());
        }

        for(int station = 1; station <= N; station++) {
            if(loopLine.contains(station)) {
                sb.append(0).append(' ');
                continue;
            }

            sb.append(getShortestDistance(station)).append(' ');
        }

        System.out.println(sb);
    }

    static int getShortestDistance(int start) {
        Queue<Station> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];

        queue.offer(new Station(start, 0));
        visited[start] = true;

        while(!queue.isEmpty()) {
            Station curStation = queue.poll();

            if(loopLine.contains(curStation.station)) return curStation.distance;

            for(int next : map.get(curStation.station)) {
                if(!visited[next]) {
                    visited[next] = true;
                    queue.offer(new Station(next, curStation.distance + 1));
                }
            }
        }

        return 0;
    }

    static void getLoopLineStations(int station, int prev, int start, boolean[] visited, ArrayList<Integer> stations) {
        if(visited[start] && start == station) {
            loopLine = new HashSet<>(stations);
            return;
        }

        for(int next : map.get(station)) {
            if(next == prev) continue;

            if(!visited[next]) {
                visited[next] = true;
                stations.add(next);

                getLoopLineStations(next, station, start, visited, stations);
                if(loopLine != null) return;

                visited[next] = false;
                stations.remove(stations.size() - 1);
            }
        }
    }

    static class Station {
        int station, distance;

        public Station(int station, int distance) {
            this.station = station;
            this.distance = distance;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 경로를 나타내기 위해 Station 클래스를 정의합니다.
  • 역을 나타내는 변수 station과 해당 역까지 이동하는데 이동한 거리를 나타내는 변수 distance를 멤버 변수로 갖습니다.

• DFS를 통해 순환선에 속하는 역들을 찾습니다.
  • 1번 역부터 N번 역까지 각 역을 시작역으로 가정하고 DFS를 진행합니다.
  • 각 역의 인접한 역들을 확인하면서 다시 시작역으로 돌아오는지 확인합니다.
  • 다시 시작역으로 돌아오는 경로를 찾아 해당 경로에 포함되는 역을 loopLine이라는 HashSet에 넣습니다.
• 1번 역부터 N번 역까지 각 역을 순회하면서 BFS를 통해 순환선까지의 거리를 구합니다.
  • 만약 해당 역이 순환선에 속하는 역이라면 거리는 0이기 때문에 해당 역은 거리를 0으로 설정합니다.
  • 순환선에 속하지 않는다면 BFS를 통해 순환선에 속하는 역 중 가장 가까운 역까지의 거리를 구합니다.