[자바]백준 11581번 구호물자 [그래프 - 플로이드 워셜][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

서론(생략가능)

이번 문제는 알고리즘 분류를 보면 dfs와 플로이드 워셜로 분류되는데 두 방법을 합쳐서 푸는 방식이 아닌 각가의 방식으로 풀 수 있는 문제이다.

1. 깊이 우선 탐색(dfs)
2. 플로이드 워셜

dfs부분은 좀 더 공부해보고 추가적으로 올릴 생각이다.

지금은 그래프 최단 경로 공부중이라 플로이드 워셜로 문제를 풀었기 때문에 2번 알고리즘을 사용해서 풀이하겠다.

 

문득 알고리즘 분류를 보지 않았으면, 이 문제를 쉽게 풀 수 있었을까? 이 문제를 보자마자 플로이드-워셜로 풀면 되겠다 생각이 들었을까? 와 같은 의문이 들었다.

 

1. dfs

그렇다면 왜 이문제가 dfs와 플로이드 워셜로 풀 수 있는 문제일까 먼저 생각해 보는 게 좋은 것 같다.

처음에 생각하면 dfs는 생각할 수 있을 것 같다.
이유는 1번에서 N번을 가는 중에 사이클이 있는지만 판별하면 되니까 1번 가는 길마다 사이클이 있는지 파악하면 되기 때문에 1->2->3->4->5 이런 식으로 깊이 있게 들어가면 된다고 생각이 든다.

 

2. 플로이드 워셜

하지만 문제는 플로이드 워셜이다.
어떤 식으로 접근하면 플로이드 워셜로 풀 수 있다는 생각이 들까?

우선, 플로이드 워셜의 특징을 한번 생각해 보자.

1. 최단 경로를 구하는 알고리즘
2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
3. 거쳐가는 정점을 기준으로 최단 거리를 구한다. (제일 큰 특징)

이번 문제는 최단 경로를 구하는 게 아니라 1번에서 도착지점은 갈 수 있고, 1번에서 갈 수 있는 정점에서 사이클이 존재하는지 안 하는지 파악하는 문제이다. 

즉, 1번에서 갈 수 있는 모든 정점, 그 정점들의 사이클 유무 이 두 가지를 알아야 한다.

정정들의 사이클 유무를 알 수 있는 방법은 벨만 포드, 플로이드 워셜이 있다.

그리고 해당 노드에서 도착 지점이 아닌 모든 정점을 파악하는 건 플로이드 워셜 한 가지만 남는다.

 

문제

서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 작동을 멈춰 제대로 된 길을 찾기란 불가능에 가까웠다.

이런 심각한 상황에 민지는 대피소에 구명 물자를 보내려고 한다. 서기 2050년 인천의 모든 길은 교차로와 도로만으로 이루어져 있다. 한 교차로와 다른 교차로는 일방통행 도로로 연결되어 있으며, 한 교차로와 여러 교차로가 연결될 수 있다. 그리고 도로에 한번 진입하면 교차로에 도착할 때까지 도로를 벗어날 수 없다.

민지는 구호물자로 가득 찬 트럭을 출발시키려고 했지만, 운행을 거부한 트럭운전사들 때문에 난관에 봉착했다. 강력한 폭풍의 영향으로 내비게이션은 정확하지 않고, 도로를 구분할 수 있는 표지판이 망가졌기 때문에 트럭운전사들은 교차로에서 어떤 도로를 선택해야 할지 모른다. 이러한 상황에서 특정 도로를 임의로 선택하면 이미 지나쳤던 교차로를 또다시 방문하는 일이 발생할 수 있고, 만약 그런 상황이 발생하면 트럭의 기름이 부족해 대피소에 도착하지 못할 수 있다.

대피소에 반드시 구호물자를 보내야 한다고 생각하는 민지는 현재 위치인 1번 교차로에서 대피소가 있는 N번 교차로까지 어떤 도로를 선택하며 가더라도 지나친 교차로를 다시 방문하지 않는다는 것을 증명해 트럭 운전사들을 설득하려 한다.

위 그림은 대피소가 3번에 있다고 했을 때 가능한 두 가지 모양이다. 왼쪽 그림에서는 어떠한 도로를 선택하더라도 지나친 교차로를 다시 방문하지 않고 대피소가 있는 3번에 무사히 도착할 수 있다. 하지만 오른쪽 그림에서는 방문했던 교차로를 다시 방문할 가능성이 있다.

민지를 도와 어떠한 길을 선택하더라도 같은 교차로를 다시 방문하는 경우가 있는지 없는지를 판단하는 프로그램을 작성하자.

 

입력

첫 번째 줄에 교차로의 수 N(1 ≤ N ≤ 100)이 주어진다. 그다음에 1번 교차로부터 N-1번 교차로의 상태가 각각 두 줄에 걸쳐 차례대로 주어진다. (1 ≤ i ≤ N-1) 번째 교차로와 연결된 교차로의 수 Mi(0 ≤ Mi ≤ N)가 주어지고 그다음 줄에는 i번째에서 갈 수 있는 교차로의 번호 Ci(1 ≤ Ci ≤ N)가 주어진다. N번 교차로는 대피소가 있는 곳이기 때문에 연결 상태가 주어지지 않는다. 구호물자가 출발하는 장소는 항상 1번이며 대피소가 있는 곳 역시 항상 N번이다.

 

출력

1번 교차로에서 N번 교차로까지 가는 과정 중 지나쳤던 교차로를 다시 방문하는 경우가 생길 수 있으면 CYCLE, 그렇지 않다면 NO CYCLE을 출력한다.

 

예제 입력 1

3
2
2 3
1
3

예제 출력 1

NO CYCLE

 

예제 입력 2

3
2
2 3
2
1 3

예제 출력 2

CYCLE

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색(dfs)
• 플로이드-워셜

 

문제 설명

아오 이 문제는 설명 서론이 너무 길다.

 

저 긴 문제는 그냥 간단하게 민지가 출발 정점(1번)에서 도달할 수 있는 정점들 중에 재방문(사이클)하게 되는 정점이 있는지 파악하라는 문제다.

 

입력 자체도 복잡하게 되어있다.

 

첫 번째 줄은 교차로의 수(정점 수)

두 번째 줄은 1번 교차로(정점)가 연결된 도로의 수(간선 수)

세 번째 줄은 1번 교차로의 도로가 연결된 교차로'들'(연결된 정점들)

.
.
.

n 번째 줄은 n-1번 교차로(정점)가 연결된 도로의 수(간선 수)

n + 1번째 줄은 n-1번 교차로의 도로가 연결된 교차로'들'(연결된 정점들)

 

또 마지막 도착지는 대피소가 있어서 연결 상태가 주어지지 않는다.

즉 1번 교차로~n-1번 교차로의 사이클만 파악하면 된다. (단, 1번 교차로가 갈 수 있는 교차로만 파악)

 

해설

이 문제는 최단 경로를 구하는 문제가 아니기 때문에 각각의 교차로가 이동했다는 표시만 남기면 되기 때문에 최단 경로 기록용 boolean[]으로 준비하면 좋다.

 

다음과 같은 풀이로 진행하자.

1. 플로이드 워셜 알고리즘을 사용해 1 교차로에서 2 교차로, 3 교차로... 등등 갈 수 있는 경로인지 기록을 남기기
2. 1 교차로에서 갈 수 있는 교차로인지 파악하고, 해당 교차로에서 사이클이 발생했는지 파악하기

코드를 보면 생각보다 쉽다는 것을 알 수 있습니다.

 

코드 보기 (플로이드 워셜)

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int n; // 교차로의 수 (정점 수)
    static boolean[][] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        arr = new boolean[n + 1][n + 1];
        
        // 데이터 초기화
        for (int i = 1; i < n; i++) {
            int e = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < e; j++) {
                int num = Integer.parseInt(st.nextToken());
                arr[i][num] = true;
            }
        }
        
        // 플로이드 워셜 알고리즘 사용해 기록 남기기
        for (int k = 1; k < n; k++) {
            for (int i = 1; i < n; i++) {
                for (int j = 1; j < n; j++) {
                    if (arr[i][k] && arr[k][j]) {
                        arr[i][j] = true;
                    }
                }
            }
        }

        String ans = "NO CYCLE";
        
        // 정점 1에서 갈 수 있는 경로인지 파악하는 동시에 해당 경로에서 사이클 일어났는지 파악
        for (int i = 1; i < n; i++) {
            if (arr[1][i] && arr[i][i]) {
                ans = "CYCLE";
                break;
            }
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}