[백준]13023: ABCDE(java)

문제

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

---

풀이

dfs로 depth가 4이상인 친구관계가 존재하는지 찾는 문제였다.

적절히 백트래킹을 넣어주면된다.

0번부터 N번까지 모두 찾으며 하나라도 가능하면 1을 출력하고 강제 프로그램을 종료해주었고,

프로그램이 종료되지 않는다면 0을 출려해주었다.

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_G5_13023_ABCDE {
    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int N, M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N];
        for(int i=0; i<N; i++) {
            list[i] = new ArrayList<>();
        }
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

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

        for(int i=0; i<N; i++) {
            visited = new boolean[N];
            visited[i] = true;
            dfs(i, 0);
        }

        System.out.println(0);
    }

    private static void dfs(int num, int depth) {
        if(depth == 4) {
            System.out.println(1);
            System.exit(0);
        }

        for(int i=0; i<list[num].size(); i++) {
            int nextNum = list[num].get(i);
            if(visited[nextNum]) continue;
            visited[nextNum] = true;
            dfs(nextNum, depth+1);
            visited[nextNum] = false;
        }
    }
}