백준 JAVA11 13023번 : ABCDE

ABCDE

시간 제한	메모리 제한
2 초	512 MB

문제

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 

예제 출력 1

1

예제 입력 2

5 5
0 1
1 2
2 3
3 0
1 4

예제 출력 2

1

예제 입력 3

6 5
0 1
0 2
0 3
0 4
0 5

예제 출력 3

0

예제 입력 4

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

예제 출력 4

1

출처

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: forever900, jmkk27, memo, pjh1016
• 문제의 오타를 찾은 사람: jason9319

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

Idea.

• 5개의 노드가 재귀형태로 연결되면 1 아니면 0
  • DFS 사용
• 모든 노드에서 DFS를 수행해서 해당 관계가 있는지 탐색한다.

relationship	depth
A	1
A→B	2
B→C	3
C→D	4
D→E	5

Code.

package dfs;

import java.util.ArrayList;
import java.util.Scanner;

public class P13023_friend {
	static ArrayList<Integer>[] A;
	static boolean[] visited;
	static boolean arrive;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // node quantity
		int M = sc.nextInt(); // edge quantity
		visited = new boolean[N];
		arrive = false;
		
		A = new ArrayList[N];

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

		for (int i = 0; i < M; i++) { // save data
			int x = sc.nextInt();
			int y = sc.nextInt();

			A[x].add(y);
			A[y].add(x);
		}

		for (int i = 0; i < N; i++) { // 각 사람별로 깊이가 5인 관계가 있는지 탐색한다.
			dfs(i, 1);
			if (arrive)
				break;
		}

		if (arrive)
			System.out.println("1");
		else
			System.out.println("0");

	}

	// dfs
	private static void dfs(int nowNode, int depth) {
		if (depth == 5 || arrive) {
			arrive = true;
			return;
		}

		visited[nowNode] = true;
		for (int i : A[nowNode]) {
			if (!visited[i]) {
				dfs(i, depth + 1);
			}
		}
		visited[nowNode] = false;
	}

}