👀 문제

🎯 입력

🎯 출력

♟️ 제출

🧐 문제 풀이

이번 문제를 풀때 가장 중요한 부분은 순환 구조이다.

문제에서 주어지는 순환선을 그래프로 표현 했을 경우 cycle이 된다고 생각했다.

하지만 모든 정점을 전부 하나씩 탐색해서 시작 지점으로 돌아온다면 시간복잡도에서 옳지 못한 결과를 낼 것 같아서 한번 사이클에 포함된 정점들은 탐새하지 않도록 하는 것이 좋을 것 같았다.

위 예제의 경우 시작점은 가장 작은 번호를 가진 번호인 1으로 시작 한다.

이후 1번 정점에 연결된 정점들은 2,3번 정점이다.

dfs로 연결된 정점을 파고 든다고 가정 해보자.

1번 정점으로 시작한 dfs를 통해 모든 정점들이 cycle에 포함됨을 알 수 있다.

위의 예제 그림은 모든 정점이 cycle에 포함되어 있기 때문에 더 다양한 예제를 통해서 진행 해보겠다.

마찬가지로 1번 정점부터 탐색한다고 가정 해보겠다.

초록색 화살표가 cycle이 형성되는 부분이고 빨간색 화살표가 dfs에서의 분기점이자 cycle이 형성 되지 않는 부분이다.

정점을 탐색하면서 모든 정점을 cycle에 포함된다고 flag를 체크 해주면서 진행하고 만약 cycle을 찾았다면 dfs를 중단하고 flag 값을 그대로 가져가면 될 것이다.

만약 cycle을 찾지 못했다면 flag를 원래대로 돌려주면 될 것이다.

🫤 의문점

♟️ 시작점이 cycle에 포함되지 않는 경우

만약 1번 지점이 cycle에 해당하지 않는 다면 flag는 false로 정상적으로 반환되는지 의문이 생겼다.

2번 정점으로 가는 화살표는 더이상 연결된 정점이 존재하지 않기 때문에 dfs는 종료 될 것 이다.

3번 정점으로 가는 화살표는 5번 정점으로 간다.

5번 정점에서 화살표는 자신의 정점 즉 5번으로 되돌아 오지만 시작점의 값은 여전히 1번으로 저장하고 있으므로 cycle이 형성되지 않았다고 판단하여 모든 flag를 되돌리면서 복귀 한다.

♟️ cycle이 여러개로 형성 되어 있는 경우

만약 cycle이 한개가 아닌 여러개가 문제에 주어진다면 이때까지의 풀이방법으로 해결이 가능한지 궁금했다.

하지만 정점 N개를 만족하면서 관계선도 N개를 만족 하기 위해서의 여러가지 cycle은 이 문제를 푸는데 까지 찾아내지 못해서 패스 했다.

🫧 제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    static int N;
    static boolean[] isCycle;
    static ArrayList<Integer>[] graphs;
    static boolean[] visited;
    static int[] distFromCycle;

    static class Node{
        int num;
        int distance;

        public Node(int num, int distance) {
            this.num = num;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); //세로

        isCycle = new boolean[N + 1];
        graphs = new ArrayList[N + 1];
        distFromCycle = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            graphs[i] = new ArrayList<>();
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer stD = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(stD.nextToken());
            int e = Integer.parseInt(stD.nextToken());

            graphs[s].add(e);
            graphs[e].add(s);
        }

        for (int i=1; i<=N; i++){
            if (checkCycle_dfs(i,i,i) == true){
                //Cycle 찾기
                break;
            }
        }

        for (int i=1; i<=N; i++){
            if (isCycle[i] == false){
                distFromCycle[i] = checkDistance_bfs(i);
            }
        }

        for (int i=1; i<=N; i++){
            bw.write(distFromCycle[i] + " ");
        }
        bw.write("\n");

        bw.flush();
        bw.close();
    }

    static int checkDistance_bfs(int start){
        visited = new boolean[N + 1];
        Queue<Node> q= new LinkedList<>();
        q.offer(new Node(start,0));
        visited[start] = true;

        while (!q.isEmpty()){
            Node now = q.poll();

            if (isCycle[now.num] == true){
                return now.distance;
            }
            for (int next : graphs[now.num]){
                if (visited[next] == false){
                    visited[next] = true;
                    q.offer(new Node(next,now.distance + 1));
                }
            }
        }

        return -1;
    }

    static boolean checkCycle_dfs(int start, int prev, int now) {
        isCycle[now] = true; //현재 노드 Cycle 포함

        for (int next : graphs[now]) {
            //현재 노드와 연결된 인접 노드 탐색

            if (isCycle[next] == false) {
                //인접 노드가 현재 Cycle 탐색에 포함되지 않은 새로운 노드 라면

                if (checkCycle_dfs(start,now,next)) {
                    return true;
                }
            } else if (prev != next && next == start) {
                //이전 노드가 다음 노드가 되는 무한 반복 방지
                //다음 노드가 시작 노드 라면 Cycle을 의미
                return true;
            }
        }

        isCycle[now] = false;
        //현재 노드는 cycle가 형성되지 않고 탐색이 종료 되었음
        return false;
    }
}