[알고리즘] 백준_ABCDE - 13023

문제 설명

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을 출력한다.

문제 분석 및 해결 방법

해당 문제는 입력 받은 값들 중 5 이상의 재귀가 있는지를 구하는 문제이다. 따라서 먼저 인접 리스트에 입력받은 값들을 저장한 후 DFS를 실행해주면 된다.

조건을 보면 N의 최대 범위가 2,000이므로 시간 복잡도는 크게 고려하지 않아도 된다. DFS의 시간 복잡도는 노드 수가 V, 엣지 수가 E일 때 O(V+E)이므로 4000, 모든 노드를 진행하면 4000*2000이면 8,000,000이므로 제한 시간 내에 풀 수 있다.

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

public class Main {
    static ArrayList<Integer>[] list;
    static boolean visited [];
    static boolean result;
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        list = new ArrayList[N];
        visited = new boolean[N];
        result = false;

        for(int i=0;i<N;i++){
            list[i] = new ArrayList<Integer>();
        }

        for(int i=0;i<M;i++){
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        for(int i=0;i<N;i++){
            DFS(i,1);
            if(result) break;
        }
        // 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력
        if(result) System.out.println(1);
        else System.out.println(0);
    }
    public static void DFS(int now, int depth){
        if(depth==5||result) {
            result=true;
            return;
        }
        visited[now] = true;
        for(int i:list[now]){
            if(!visited[i]){
                DFS(i,depth+1);
            }
        }
        visited[now] = false; // 그래프가 연결되어 있지 않을 때 다른 노드에서 다시 시작할 수도 있음
    }
}

참고 : Do it! 알고리즘 코딩테스트 with JAVA