13023 ABCDE

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

예제 입력 1

5 4
0 1
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

5 5
0 1
1 2
2 3
3 0
1 4

예제 출력 2

1

예제 입력 3

6 5
0 1
0 2
0 3
0 4
0 5

예제 출력 3

0

예제 입력 4

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

예제 출력 4

1

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;

public class P_13023 {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static boolean status;

    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[] friend_info = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        graph = new ArrayList[friend_info[0]];
        for (int i = 0; i < friend_info[0]; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < friend_info[1]; i++) {
            int[] friend = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int from = friend[0];
            int to = friend[1];

            graph[from].add(to);
            graph[to].add(from);
        }

        for (int i = 0; i < friend_info[0]; i++) {
            if (!status) {
                visited = new boolean[friend_info[0]];
                dfs(i, 1);
            }
        }

        if (status) bw.write(Integer.toString(1));
        else bw.write(Integer.toString(0));
        bw.flush();
    }

    public static void dfs(int idx, int depth) {
        if (depth == 5) {
            status = true;
            return ;
        }
        else {
            visited[idx] = true;
            for (int num : graph[idx]) {
                if (!visited[num]) dfs(num, depth + 1);
            }
            visited[idx] = false;
        }
    }
}

코드 설명

문제에서 요구하는 것은 A-B-C-D-E가 만족하는가이다.
최소 다섯 명이 연결된 친구 사이어야 한다는 말이다.

그러므로 DFS를 이용했다.

그래프는 arraylist 자료형을 이용했는데 배열을 선언하고 각 인덱스마다 arraylist 자료형을 갖도록 했다.

친구가 된다는 것은 무방향 간선 그래프이므로 두 개의 정점이 주어지면 두 개의 인덱스에 모두 추가를 해 주었다.

dfs는 모든 정점을 출발지로 시작할 수 있기 때문에 정점마다 dfs를 호출한다.
dfs 메소드는 참조할 인덱스인 idx와 순회의 깊이를 나타내는 depth 인자를 갖는다.
이 depth가 5가 되면 5명의 친구가 있다는 뜻으로 status를 true로 변경한 후 dfs를 종료한다.

visited는 해당 정점을 방문했는지 여부를 확인한다.
true일 경우 방문했다는 것을 나타내고, false일 경우 방문하지 않았다는 것을 나타낸다.
dfs는 해당 idx에 대해서 visited를 true로 만들어주는 것을 시작으로 한다.
그리고 해당 idx에 대해서 연결된 모든 정점을 순회를 하는데 확인하는 정점에 대한 visited가 false일 경우 다시 dfs함수를 호출한다.

이 문제는 모든 그래프를 순회했을 때 5명의 친구가 있는 것인지 확인하는 것이기 때문에 순회가 끝나면 visited를 false로 바꾸어준다.