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

문제 링크

16947번: 서울 지하철 2호선

 

풀이 ) DFS

1. 각 역이 순환선에 포함된 역인지 확인
2. 사이클에서 지선이 있는 역에서부터 각 지선 노선의 거리 구하기

위의 순서대로 DFS만을 이용해서 구했다.

 

  먼저 각 역이 순환선인지 확인하기 위해 모든 점에 대해서 현재 점으로 되돌아 오는지 확인했다. (checkCycle()) 이때 순환선을 확인하면 순환선 내의 역은 한번에 구해 반복 횟수를 줄일 수 있다. (return type이 boolean인 이유)

 

  순환역에 속한 역 중 차수가 3 이상인 역은 지선으로 갈 수 있는 역이므로 이 역을 시작으로해서 지선에 포함된 역까지의 거리를 구한다. (getDistance())

 

코드 )

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

class Main {

    static int n;
    static List<Integer>[] adj;
    static boolean[] visited;
    static boolean[] isCycle;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        input();
        checkCycle();	// 사이클 확인
        getDistance();	// 거리 구하기
    }

    static void getDistance() {
        distance = new int[n+1];
        visited = new boolean[n+1];

		// 사이클에서 벗어나는 길 거리 구하기
        for(int i = 1; i <= n; ++i)
            if(isCycle[i] && adj[i].size() > 2)
                searchRoute(i);

		// 거리 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= n; ++i) {
            sb.append(distance[i] + " ");
        }
        System.out.println(sb.toString());
    }

    static void searchRoute(int i) {
        for(int next: adj[i]) {
            if(isCycle[next] || distance[next] > 0) {
               continue;
            }
            distance[next] = distance[i]+1;
            searchRoute(next);
        }
    }

    static void checkCycle() {
        isCycle = new boolean[n+1];

        for(int i = 1; i <= n; ++i)
            if(!isCycle[i]) {
                visited = new boolean[n+1];
                dfs(i, i, 0);
            }
    }

    static boolean dfs(int strt, int i, int cnt) {
        for(int next: adj[i]) {
            if(next == strt) {
            // 바로 돌아오는 경우를 cnt를 사용해서 방지
                if (cnt > 1)
                    return isCycle[i] = true;
                else
                    continue;
            }
            
            // 다음이 사이클(사이클이 아닌 곳에서 사이클로 -> 사이클 아님)
            // 현재가 사이클(조건 만족)
            // 이미 방문(사이클인지 여부가 이미 나옴)
            if(isCycle[next] || isCycle[i] || visited[next])
                continue;
            visited[next] = true;
            isCycle[i] = dfs(strt, next, cnt+1);
        }
        return isCycle[i];
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        adj = new List[n+1];
        for(int i = 1; i <= n; ++i)
            adj[i] = new ArrayList<>();
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            // 양방향
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            adj[v1].add(v2);
            adj[v2].add(v1);
        }
    }
}

 

알게된 점 )

  그래프에서 정점과 간선의 개수가 같고 모두 이어져 있으면 사이클은 단 하나만 가능하다.