ABCDE (백준 13023) [JAVA]

 

문제

문제 링크 : www.acmicpc.net/problem/13023

13023번: ABCDE

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	512 MB	9609	2823	1893	28.343%

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로 풀어야 하는 문제이다. 5명만 탐색하면 되기 때문에 체크하다가 5명이면 탈출하면 된다.

N번씩 깊이 5만큼 DFS를 시도하므로 $N*N^5$, $O(N^6)$인 것 같다. 이때 이는 엄청 큰 수이므로, 적절하게 탈출조건을 만들어주는게 중요한 것 같다.

깊이 5라 재귀로 하는게 훨씬 편함에도 스택으로 처음에 시도했었다.

스택으로 할때는, path를 되돌리기 위해 현재 위치를 호출한 위치를 기억하고, 이 호출한 위치에서 호출한 횟수를 연산해 다 깎이면 path를 1 줄이는 복잡한 방식으로 하고, 매 시도마다 초기화해야할 변수들이 많아서 시간초과와 오답 퍼레이드를 맞았다.

DFS라 하더라도 재귀의 깊이를 빠르게 파악해 재귀로 할지, 스택으로 할지 빠르게 판단해서 하는 것이 중요하다는 것을 느꼈다.

 

코드

import java.util.Scanner;

public class Main {
	
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static int[][] friends;
    public static int[] friends_checked;
    public static int[] friends_num;
    public static int ans;
    public static void main(String[] args)throws Exception {
    	Scanner sc = new Scanner(System.in);
    	int N = sc.nextInt();
    	
    	friends = new int[N][N];
    	friends_checked = new int[N];
    	friends_num = new int[N];
    	
    	int M = sc.nextInt();
    	
    	//배열 초기화
    	for(int i=0; i<N; i++) {
    		for(int j=0; j<N; j++) {
    			friends[i][j] = 0;
    		}
    	}
    	for(int x=0; x<N; x++) {
    		friends_checked[x] = 0;
    	}
    	for(int x=0; x<N; x++) {
    		friends_num[x] = 0;
    	}
    	
    	//친구관계 만들기
    	for(int i=0; i<M; i++) {
    		int a =  sc.nextInt();
    		int b =  sc.nextInt();
    		friends[a][b] = 1; friends[b][a] = 1;
    		friends_num[a]++; friends_num[b]++;
    	}
        
    	ans = 0;
    	for(int i=0; i<N; i++) {
    		if(friends_num[i] == 0) continue;
    		DFS(i,N,1);
    		if(ans == 1) break;
    	}
    	System.out.println(ans);
    }
    
    public static void DFS(int idx, int N, int path){
    	if(path == 5) {ans = 1; return;}
    	
    	friends_checked[idx] = 1;
    	for(int i=0; i<N; i++) {
    		if(path > 1) {
    			if(friends_num[idx] == 1) break;
    		}
    		if((friends[idx][i] == 1) && (friends_checked[i] == 0)) {
    			DFS(i,N,path+1);
    		}
    	}
    	friends_checked[idx] = 0;
    }
}

 

결과