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

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

16947번: 서울 지하철 2호선

풀이

그래프의 탐색과 관련된 문제였다. 탐색 관련한 알고리즘을 활용하여 문제를 풀었다. 

 

🤗 우선 풀이 과정을 다음과 같은 순서로 나눠 구현해 주었다.

1. 싸이클이 발생하는 구간을 체크해준다.
2. 탐색을 통해 모든 노드에서 싸이클이 발생하는 노드까지의 거리를 계산해 준다.

하나씩 차근차근 살펴보장.

 

🔹 싸이클이 발생하는 구간을 체크해준다.

싸이클은 언제 발생할까? 🤔 

👉 그래프의 특성을 알고 있다면 쉽게 생각해 낼 수 있다. 처음 방문했던 노드를 다시 방문하게 될 때 싸이클이 발생한다. 

 

그러므로, 모든 노드를 차례대로 확인하며 싸이클이 발생하는 노드를 확인하고, 싸이클이 발생했다면 해당 노드가 싸이클에 포함된 노드라는 표시를 남겨준다. 이를 위해 isCycle배열을 선언해 활용하였다.

 

싸이클 노드인지 확인하는 함수는 checkCycle함수로 구현해 주었다. 

바로 이전의 방문했던 노드와 현재 노드, 시작 노드의 정보를 가지고 싸이클 노드인지 확인해 주었다. 구현 방법을 자세히 알아보자.

1. 먼저 현재 노드의 싸이클을 true값으로 설정한다.
2. 현재 노드와 연결된 노드를 탐색한다.
3. 연결된 노드중에 아직 싸이클 체크하지 않은 노드가 있다면 해당 노드로 탐색을 진행한다.
4. 연결된 노드가 바로 이전에 방문한 노드가 아니며(자기 자신으로 오는 경우 제외하기 위함) 연결된 노드가 시작 노드라면 처음 방문했던 노드를 재 방문한 것이므로 싸이클이 발생한 것이다.

 

위와 같은 방식으로 깊이우선 탐색을 진행해 주었다.

 

🔹 싸이클이 발생하는 노드까지의 거리를 계산해 준다.

이 부분의 코드는 dfs, bfs 자신에게 더 편한 어느 방법으로 구현해 주어도 상관없다. 이 문제에서는 최소 거리를 구해야 함으로 bfs로 구해주었다. 

 

모든 노드에서 부터 탐색을 진행하다가 싸이클에 포함된 노드를 발견하면 현재 count를 반환하도록 구현하였다. 이 부분은 전형적인 탐색 알고리즘을 활용하여 구현하면 된다.

 

코드

import java.util.*;
 
public class Main {
 
    static ArrayList<Integer>[] list;
    static int n;
    static boolean[] isCycle;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
 
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
 
        for(int i = 0; i < n; i++) {
            int n1 = scan.nextInt();
            int n2 = scan.nextInt();
            list[n1].add(n2);
            list[n2].add(n1);
        }
 
        //싸이클을 찾아 표시해준다.
        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] + " ");
    }
 
    public static int bfs(int node) {
        Queue<Node> q = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        q.add(new Node(node, 0));
        visited[node] = true;
 
        while(!q.isEmpty()) {
            Node current = q.poll();
            if(isCycle[current.v]) return current.count;
 
            for(int i = 0; i < list[current.v].size(); i++) {
                int next = list[current.v].get(i);
                if(!visited[next]) {
                    visited[next] = true;
                    q.add(new Node(next, current.count + 1));
                }
            }
        }
        return 0;
    }
 
    public static boolean checkCycle(int prev, int node, int start) {
        isCycle[node] = true;
 
        for(int i = 0; i < list[node].size(); i++) {
            int next = list[node].get(i);
 
            if(!isCycle[next]) {
                if(checkCycle(node, next, start)) return true;
            } else if(next != prev && next == start) return true;
        }
        isCycle[node] = false;
        
        return false;
    }
 
    public static class Node {
        int v;
        int count;
 
        public Node(int v, int count) {
            this.v = v;
            this.count = count;
        }
    }
}