[PS] BOJ16947 서울 지하철 2호선 ( DFS ) with JAVA

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

16947번: 서울 지하철 2호선

 

 

◎ 문제풀이 

 

그래프에서 싸이클을 찾고 싸이클과 노드 사이의 거리를 구하는 문제이다. 

 

풀이과정은 3가지 STEP으로 진행된다.

 

STEP1) 그래프를 인접리스트로 구현

STEP2) 싸이클 DFS 알고리즘으로 탐색하기

STEP3) 싸이클과 노드사이의 거리를 DFS로 구하기

 

- 싸이클 DFS 알고리즘으로 탐색하기

 

싸이클은 DFS, BFS로 탐색이 가능하다. 문제에서 싸이클은 1개만 존재한다고 했으니 깊이우선탐색(DFS)으로 싸이클을 찾으면, 바로 탐색을 종료하는 방식으로 진행하면 된다. 싸이클 탐색 과정에서 싸이클 경로에 있던 노드는 싸이클에 포함된 노드임을 표시로 남긴다. 

 

- 싸이클과 노드사이의 거리를 DFS로 구하기

 

싸이클에 포함된 노드는 표시가 남겨져 있으니, 이들 노드는 거리가 0이다. 표시가 남겨지지 않은 노드는 DFS로 싸이클과의 거리를 계산해야 한다. 인접노드를 탐색하며 싸이클 표식이 있는 노드를 찾으면 된다. 싸이클 노드를 찾으면 DFS 탐색 깊이로 거리를 계산한다. 

 

◎ 코드 

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

//BOJ16947 서울 지하철 2호선
public class Main {
    static Node[] nodes; // 그래프
    static boolean[] visited; // 방문여부 테이블

    //Node 데이터
    public static class Node{
        int index; // Node의 index
        boolean isCycle; // 싸이클에 Node 포함 여부
        int dist; // 싸이클과의 거리
        List<Node> nextNodes = new ArrayList<>(); // 인접노드 리스트

        public Node(int index){
            this.index = index;
        }
    }
    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());
        nodes = new Node[n+1]; // 그래프 생성
        visited = new boolean[n+1]; // 방문여부 테이블 생성

        // STEP1. 그래프를 인접리스트로 구현하기
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i); // 그래프 초기화
        }

        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            // 인접리스트에 데이터 세팅하기
            nodes[a].nextNodes.add(nodes[b]); // 양방향 그래프
            nodes[b].nextNodes.add(nodes[a]); // 양방향 그래프
        }

        // STEP2. 싸이클 찾기 ( DFS )
        for(int i=1;i<n+1;i++){
            visited[i] = true;
            if(findCycle(nodes[i],nodes[i],1)) break; // 싸이클은 1개 이므로 찾으면 break
            visited[i] = false;
        }

        // STEP3. 싸이클과의 거리 계산하기 ( DFS )
        for(int i=1;i<=n;i++){
            if(nodes[i].isCycle) nodes[i].dist = 0; // 싸이클에 포함되어 있는 Node의 경우, 거리 = 0
            else{ // 싸이클에 포함되어 있지 않은 경우, DFS로 거리 계산하기
                visited = new boolean[n+1];
                visited[i] = true;
                setDist(nodes[i],nodes[i],0);
            }
        }

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++){
            sb.append(nodes[i].dist).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    // 싸이클 찾기 DFS
    public static boolean findCycle(Node node, Node startNode, int depth){

        for (Node nextNode : node.nextNodes) {
            if(depth > 2 && nextNode == startNode) { // 다음 노드가 시작노드이면 순환 탐색 완료
                node.isCycle = true; // 싸이클에 포함 true
                return true;
            }
            if(!visited[nextNode.index]) {
                visited[nextNode.index] = true; // 방문이력 남기기
                if (findCycle(nextNode, startNode, depth + 1)) {
                    node.isCycle = true; //싸이클에 포함 true
                    return true;
                }
                visited[nextNode.index] = false; // DFS 종료 후, 방문이력 지우기
            }
        }
        return false; // 싸이클을 찾지 못하면 false 반환
    }

    // 싸이클과의 거리 계산하기 DFS
    public static void setDist(Node node, Node startNode, int depth){
        if(node.isCycle) { // 지선은 경로가 하나이므로, 싸이클을 만나면 바로 종료
            startNode.dist = depth; // DFS 깊이로 싸이클과의 거리 구하기
            return;
        }

        // 싸이클에 포함된 노드를 발견하지 못하면 DFS 탐색
        for( Node nextNode : node.nextNodes ) {
            if(!visited[nextNode.index]){
                visited[nextNode.index] = true; // 역행 방지
                setDist(nextNode,startNode,depth+1); // DFS 탐색
            }
        }
    }

}