[Java] BOJ/백준 16947번 서울 지하철 2호선

[문제]

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

16947번: 서울 지하철 2호선

 

[풀이]

이 문제는 1) 사이클이 발생하는 구간을 구할 수 있는지, 2) 그래프 탐색으로 최단 거리를 구할 수 있는지 를 판단하는 문제이다.

 

따라서 아래와 같은 순서로 문제를 풀었다.

1. DFS 탐색을 통해 사이클이 발생하는 구간을 체크한다.

2. BFS 탐색을 통해 모든 노드에서 사이클이 발생하는 노드까지의 최단 거리를 계산한다.

 

1️⃣ 사이클 발생 구간 체크

사이클은 언제 발생할까? 처음 방문했던 노드를 다시 방문해야 될 때 사이클이 발생한다.

 

따라서 1부터 N까지 모든 노드를 순회해 사이클이 발생하는 노드를 확인하고, 사이클 발생 시 isCycle 배열에 사이클이라는 표시를 남겨둔다.

boolean[] isCycle = new boolean[N + 1];
for (int i = 1; i <= N; i++) {
    if (checkCycle(i, i, i)) break;
    isCycle = new boolean[N + 1];
}

 

사이클 노드인지 확인하는 checkCycle 메서드는 (직전 방문 노드, 현재 노드, 시작 노드)를 통해 해당 경로가 사이클인지 확인한다.

1. 현재 노드의 사이클 값을 true로 설정한다.

2. 현재 노드와 연결된 노드 중 아직 사이클 체크를 하지 않은 노드(방문하지 않은 노드) 일 경우만 dfs 탐색한다.

3. 연결된 노드가 사이클 체크된 노드인데(이미 방문한 노드), 직전에 방문했던 노드가 아니고(방금 왔던 길을 다시 돌아오는 경우) 시작 노드인 경우 해당 경로는 사이클 경로이다. (처음 방문 노드를 재방문한 것이기 때문)

private static boolean checkCycle(int prev, int cur, int start) {
    isCycle[cur] = true;
    for (int i = 0; i < subway[cur].size(); i++) {
        int next = subway[cur].get(i);

        if (!isCycle[next]) {
            if (checkCycle(cur, next, start)) return true;
        } else if (prev != next && next == start) return true;
    }
    isCycle[cur] = false;

    return false;
}

 

2️⃣ 사이클이 발생하는 노드까지의 거리 계산

해당 계산은 깊이 우선 탐색이나 너비 우선 탐색 중 어떤 방법으로 구현해도 상관없지만, 최단 거리 문제이기 때문에 너비 우선 탐색으로 구현해 주었다.

int[] result = new int[N + 1];
for (int i = 1; i <= N; i++) {
    if (!isCycle[i]) result[i] = bfs(i);
}

1부터 N까지의 노드(모든 노드)에서 사이클이 아닌 노드일 경우 bfs 탐색을 통해 사이클 노드까지의 거리를 구한다.

 

private static int bfs(int node) {
    Queue<Node> queue = new LinkedList<>();
    boolean[] visited = new boolean[N + 1];
    queue.offer(new Node(node, 0));
    visited[node] = true;

    while (!queue.isEmpty()) {
        Node now = queue.poll();
        if (isCycle[now.vertex]) return now.count;

        for (int next : subway[now.vertex]) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(new Node(next, now.count + 1));
            }
        }
    }
    return 0;
}

큐에 현재 노드와 count를 넣고 bfs 탐색 중 사이클 경로에 포함된 노드(isCycle 값이 true인 노드)인 경우 현재 count 값을 반환한다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static ArrayList<Integer>[] subway;
    static int N;
    static boolean[] isCycle;

    static class Node {
        int vertex, count;

        public Node(int vertex, int count) {
            this.vertex = vertex;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        subway = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) subway[i] = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            subway[a].add(b);
            subway[b].add(a);
        }

        isCycle = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            if (checkCycle(i, i, i)) break;
            isCycle = new boolean[N + 1];
        }

        int[] result = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            if (!isCycle[i]) result[i] = bfs(i);
        }

        for (int i = 1; i <= N; i++) System.out.print(result[i] + " ");
    }

    private static int bfs(int node) {
        Queue<Node> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        queue.offer(new Node(node, 0));
        visited[node] = true;

        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (isCycle[now.vertex]) return now.count;

            for (int next : subway[now.vertex]) {
                if (!visited[next]) {
                    visited[next] = true;
                    queue.offer(new Node(next, now.count + 1));
                }
            }
        }
        return 0;
    }

    private static boolean checkCycle(int prev, int cur, int start) {
        isCycle[cur] = true;
        for (int i = 0; i < subway[cur].size(); i++) {
            int next = subway[cur].get(i);

            if (!isCycle[next]) {
                if (checkCycle(cur, next, start)) return true;
            } else if (prev != next && next == start) return true;
        }
        isCycle[cur] = false;

        return false;
    }
}