[BOJ] 백준 13023번 ABCDE (Java)

#13023 ABCDE

난이도 : 골드 5

유형 : 그래프 / DFS  

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

 

문제 풀이  

그래프 문제로 DFS를 이용하여 풀이를 할 수 있다.  한가지 주의해야할 부분은 깊이 위주 탐색이다보니 경로에 대한 유연성이 부족하는 점이다. 그래서 모든 노드를 다시 되돌아가는 기법을 사용해야 한다. 즉, 시작점으로부터 연결되어있는 모든 간선을 탐색해줘야 한다는 뜻이다.

 

만약 단순 DFS을 할 경우 반례는 다음과 같다. 해당 그래프는 1을 출력해야 정답이다. 하지만 단순 DFS탐색은 0을 출력하게 된다. 깊이탐색이기 때문에 0에서 제일 깊은 4까지 제일 빠른 경로로 탐색하기 때문이다. 

static void dfs(int idx, int depth) {
	if(depth==5) {
		status=true;
		return;
	}

	check[idx]= true;
	for(int nxt : list[idx]) {
		if(!check[nxt]) {
			dfs(nxt, depth+1);
		}
	}
}

단순 DFS할 경우 반례

 

따라서, 다음 그림과 같이 DFS 탐색에 check[idx] = false;를 추가하여 DFS탐색이 유연성있게 모든 경로를 탐색할 수 있도록 해준다. 그러면 다음과 같이 올바른 답을 찾아 1을 출력하는 것을 확인할 수 있다.

static void dfs(int idx, int depth) {
	if(depth==5) {
		status=true;
		return;
	}

	check[idx]= true;
	for(int nxt : list[idx]) {
		if(!check[nxt]) {
			dfs(nxt, depth+1);
		}
	}
	check[idx]= false; // 추가
}

 

모든 경로 탐색

 

 

설계

1. 0~n-1번 노드를 차례대로 DFS탐색을 한다. for i :0 ~n-1, dfs(i,1);
   1. 만약 해당 노드가 ABCDE관계를 맺는 노드라면, 1을 출력하고 탐색을 종료한다.
   2. 만약 ABCDE관계가 없다면, 다른 노드를 탐색한다. 만약 전체 탐색을 해도 없다면 0을 출력한다.

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static boolean status;
	static List<Integer>[] list;
	static boolean[] check;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int 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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}

		status = false;
		for(int i=0; i<n; i++) {
			check = new boolean[n];
			dfs(i,1);
            if(status) {
				System.out.println(1);
				return;
			}
		}
		System.out.println(0);
	}
	
	static void dfs(int idx, int depth) {
		if(depth==5) {
			status=true;
			return;
		}
		check[idx]= true;
		for(int nxt : list[idx]) {
			if(!check[nxt]) {
				dfs(nxt, depth+1);
			}
		}
        check[idx]= false;
	}
}