[JAVA, 백준] 16947. 서울 지하철 2호선

문제는 아래 링크를 참고해주세요.

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

16947번: 서울 지하철 2호선

 

문제 풀 때 기억하기

술술 풀린 문제보다 술술 풀리지 않은 문제에 집중한다.

문제 풀 때 지키기

1. 30분 타이머를 재고 고민한다.

2. 고민할 때는 주석 혹은 필기를 하며 본인 생각을 정리한다.

3. 30분이 지나고도 아이디어가 떠오르지 않으면 다른 사람 풀이를 찾아본다.

4. 오답노트 적듯이 나의 전개와 다른 점을 찾아서 부족한 부분을 인지한다.

 

제가 생각한 로직은 다음과 같습니다.

1. 순환선을 체크해야 한다. 이때 포함되는 역은 distance 배열에 0을 입력한다.
2. 순환선에 포함되지 않는 역은 거리차를 체크하여 distance 배열에 입력한다.

문제는.. 30분 내에 구현에 대한 아이디어가 떠오르지 않았다는 점이네요😭

추가로, 지문을 봤을 때는 순환선이 1개만 있는 상황이라고 확신하기 힘들었습니다.

 

구글링을 하니 2개정도의 풀이가 대체로 보였습니다.

제가 선택한 방법은

1. 모든 연결된 노드들을 깊이 끝까지 우선 탐색하며 (조건에 따라) 순환선을 체크하는 방식으로 구현합니다.

2. 큐의 노드들을 탐색하는데 해당 노드들의 인접 노드들을 체크하며 거리를 ++하고, 순환선에 포함된 노드를 만날 시 증가된 거리를 리턴하는 방식으로 답을 구합니다.

 

제일 효율적인 로직은 아닐 수 있지만 제 수준에서 더 이해되는 로직으로 풀어보고자 합니다.

 

풀이

우선,

준비 : 사용자로부터 input을 받은 값으로 인접리스트를 생성합니다.

public class Solution {
	static int N;
    static List<Integer>[] adj;
    static int[] distFromCycle; // 차후에 사용됩니다.
    static boolean[] visited;	// 차후에 사용됩니다.
    static boolean[] isCycle;	// 차후에 사용됩니다.
    private static void input() throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        adj = new ArrayList[N];
        for (int i=0; i<N; i++) adj[i] = new ArrayList<>();
        StringTokenizer st;
        // 인접리스트 생성
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int nodeA = Integer.parseInt(st.nextToken())-1;
            int nodeB = Integer.parseInt(st.nextToken())-1;
            adj[nodeA].add(nodeB);
            adj[nodeB].add(nodeA);
        }
    }
    // ..
}

 

순환선 체크 : 연결된 노드들을 탐색하면서 순환선을 찾는 과정을 적어봅시다.

모든 노드를 방문하면서 순환선이 있는지 탐색합니다. (싸이클이 있다면 true를 리턴합니다.)

다른 글에서는 아래 for문 내에서 Cycle을 못찾을 시 (else문) isCycle 배열을 리셋해주는데 어짜피 Cycle을 못만나는 경우 checkCycle_dfs 메서드에서 false 처리 해주므로 리셋해주지 않아도 됩니다.

public static void main(String[] args) throws IOException {
        // 1. 준비
        input();
        /** 추가 **/
        // 2. 각 역에 대해 순환선(싸이클) 체크 (깊이 우선으로 모든 노드 탐색)
        isCycle = new boolean[N];
        for (int i=0; i<N; i++) {
            if(checkCycle_dfs(i, i, i)) break;  // Cycle이면 stop
        }
        
        // 3번째 로직..

 

그럼 바로 checkCycle_dfs 메서드를 작성해보겠습니다.

각 노드에 대해서 탐색해서 순환선이 있는지 체크하므로 

1. 시작 노드의 isCycle을 true로.

2. 해당 노드의 인접 노드들을 반복문으로 탐색하면서

• Cycle이 아니면 그 노드의 인접 노드들을 시작노드로 다시 Cycle이 있는지 탐색합니다.
• Cycle 표시가 되어있고 만약 시작 노드이면서, 현재 노드가 이전 노드가 아니면! Cycle의 시작 노드인 것이므로 true를 리턴합니다.

3. for문 내에서 return true를 하지 못했으니 다시 isCycle을 false 처리하고 false를 반환합니다.

private static boolean checkCycle_dfs(int start, int prev, int now) {
    isCycle[now] = true;    // 사이클 체크
    for (int adjNode: adj[now]) { // 연결된 노드에 방문
        // cycle이 아니면
        if (!isCycle[adjNode]) {
            if(checkCycle_dfs(start, now, adjNode)) return true;
        } else if (prev != adjNode && start == adjNode) return true;    // 싸이클인데 시작 노드이면 종료
    }
    isCycle[now] = false;        // cycle을 못만나면
    return false;
}

 

 

최소 거리 체크 : 순환선을 찾은 상태에서 그외 노드들의 거리를 체크합시다.

// 3. 최소 거리 체크 (인접 노드들의 순환포함 체크 후 거리 지정 및 ++)
distFromCycle = new int[N];
for (int i=0; i<N; i++) {
    visited = new boolean[N]; // 매 거리 체크마다 방문 리셋
    // cycle에 포함X 노드 발견 시
    if (!isCycle[i]) distFromCycle[i] = computeDist(i);
}

 

거리를 체크할 배열을 생성하고,

마찬가지로 각 노드들을 순환하면서 cycle에 포함되지 않은 노드인 경우 computeDist 메서드를 호출합니다.

computeDist 에서는 특정 노드의 인접노드들을 방문하면서 Cycle 에 포함된 노드를 만날 때까지의 거리를 구해서 반환합니다.

매 반복마다 그 값에 해당하는 (Cycle에 포함되지 않은) 노드의 거리를 구할 수 있습니다.

한번 computeDist 메서드를 호출할 때 하나의 노드에 대한 거리만 구하는 점에서 아쉬운 느낌이라

더 효율적인 방법이 있을 것 같다는 생각이 드네요 🤔

// 인접 노드 중 cycle에 포함된 노드 만날때까지 거리++
private static int computeDist(int now) {
    Queue<Node> q = new LinkedList<>();
    q.add(new Node(now, 0));
    while (!q.isEmpty()) {
        Node node = q.poll();
        if (isCycle[node.num]) return node.dist;
        for (int adjN : adj[node.num]) {
            if (!visited[adjN]) {
                visited[adjN] = true;
                q.add(new Node(adjN, node.dist+1)); // 현재 노드의 인접이니까 거리+1
            }
        }
    }
    return 0;
}

 

추가로, 특정 노드의 인접한 노드들에 방문하면서 Cycle에 포함되는 노드를 만나기까지의 거리값을 구할 때

해당 노드의 거리값이 증가해야 하고, 그 노드의 번호도 필요하기 때문에 Node라는 클래스를 생성하여 사용했습니다.

static class Node {
    private int num;
    private int dist;
    public Node(int n, int d) {
        this.num = n;
        this.dist = d;
    }
}

 

 

전체 코드 (JAVA)

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

public class Solution {
    static int N;
    static List<Integer>[] adj;
    static int[] distFromCycle;
    static boolean[] visited;
    static boolean[] isCycle;
    public static void main(String[] args) throws IOException {
        // 1. 준비
        input();
        // 2. 각 역에 대해 순환선(싸이클) 체크 (깊이 우선으로 모든 노드 탐색)
        isCycle = new boolean[N];
        for (int i=0; i<N; i++) {
            if(checkCycle_dfs(i, i, i)) break;  // Cycle이면 stop
        }
        // 3. 최소 거리 체크 (인접 노드들의 순환포함 체크 후 거리 지정 및 ++)
        distFromCycle = new int[N];
        for (int i=0; i<N; i++) {
            visited = new boolean[N]; // 매 거리 체크마다 방문 리셋
            // cycle에 포함X 노드 발견 시
            if (!isCycle[i]) distFromCycle[i] = computeDist(i);
        }
        StringBuilder sb = new StringBuilder();
        for (int i:distFromCycle) sb.append(i).append(" ");
        System.out.println(sb);
    }

    private static void input() throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        adj = new ArrayList[N];
        for (int i=0; i<N; i++) adj[i] = new ArrayList<>();
        StringTokenizer st;
        // 인접리스트 생성
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int nodeA = Integer.parseInt(st.nextToken())-1;
            int nodeB = Integer.parseInt(st.nextToken())-1;
            adj[nodeA].add(nodeB);
            adj[nodeB].add(nodeA);
        }
    }
    private static boolean checkCycle_dfs(int start, int prev, int now) {
        isCycle[now] = true;    // 사이클 체크
        for (int adjNode: adj[now]) { // 연결된 노드에 방문
            // cycle이 아니면
            if (!isCycle[adjNode]) {
                if(checkCycle_dfs(start, now, adjNode)) return true;
            } else if (prev != adjNode && start == adjNode) return true;    // 싸이클인데 시작 노드이면 종료
        }
        isCycle[now] = false;        // cycle을 못만나면
        return false;
    }
    // 인접 노드 중 cycle에 포함된 노드 만날때까지 거리++
    private static int computeDist(int now) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(now, 0));
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (isCycle[node.num]) return node.dist;
            for (int adjN : adj[node.num]) {
                if (!visited[adjN]) {
                    visited[adjN] = true;
                    q.add(new Node(adjN, node.dist+1)); // 현재 노드의 인접이니까 거리+1
                }
            }
        }
        return 0;
    }
    static class Node {
        private int num;
        private int dist;
        public Node(int n, int d) {
            this.num = n;
            this.dist = d;
        }
    }
}

 

 

잘못된 부분에 대한 피드백과
댓글은 환영입니다‼️