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

[ 시간복잡도 ]

 

[ 핵심풀이 ]

◎ DFS

A→ B →C →D →E로 한 점에서시작해 4개의 친구가 연결되어있는지 확인하면 된다.

[ 핵심소스 ]

1) 4개이상의 연결된 때가 존재하면 return

2) 4개이상이 연결됐다면 연결상태를 True로 변경하고 리턴

static void solve(int index, int cnt) {
    if (result) return;
    if (cnt==4) {
        result=true;
        return;
    }
    for(Integer item : v[index]) {
        if (!visit[item]) {
            visit[item]=true;
            solve(item, cnt+1);
            visit[item]=false;
        }
    }
}

[ Java ]

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

class load {
	int index;
	int cnt;
}
public class Main {
    static int friend;
    static int relation;
    static boolean visit[] = new boolean[2005];
    static Vector<Integer> v[] = new Vector[2005];
	
    static boolean result = false;
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        friend = sc.nextInt();
        relation = sc.nextInt();
		
        init();
		
        for (int i = 0; i < relation; i++) {
            int fs = sc.nextInt();
            int se = sc.nextInt();
            v[fs].add(se);
            v[se].add(fs);
        }
		
        for(int i=0;i<friend;i++) {
            if (result) {
                System.out.println(1);
                return;
            }
            Arrays.fill(visit,false);
            visit[i]=true;
            solve(i, 0);
        }
        System.out.println(0);
        sc.close();
    }
    static void init() {
        for(int i=0;i<friend;i++)
            v[i] = new Vector<Integer>(2005);
    }
	
    static void solve(int index, int cnt) {
        if (result) return;
        if (cnt==4) {
            result=true;
            return;
        }
        for(Integer item : v[index]) {
            if (!visit[item]) {
                visit[item]=true;
                solve(item, cnt+1);
                visit[item]=false;
            }
        }
    }
}