[Java] BOJ13023, 백준 - ABCDE

https://www.acmicpc.net/problem/13023

13023번: ABCDE

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512MB	14174	4274	2859	29.147%

문제

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. 인접 리스트 배열을 만들어서 입력되는 친구 관계를 인접 리스트에 저장한다.
2. 저장된 인접 리스트를 바탕으로 연결된 노드들을 순회한다.
   1. 인접 노드가 있을 경우 DFS를 통해 그래프를 탐색하며 5명의 친구 관계가 이어져있는지 찾는다.
   2. 5개 이상 이어져있을 경우 1을 출력하고 프로그램을 종료한다.
3. 끝까지 찾았는데 5개 이상인 연결 관계가 없을 경우 0을 출력하고 종료한다.

 

소소코드

import java.io.*;
import java.util.*;

public class Main {

	private static ArrayList<Integer>[] arr;
	private 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());
		arr = new ArrayList[n];
		for (int i = 0; i < n; i++)
			arr[i] = new ArrayList<Integer>();

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a].add(b);
			arr[b].add(a);
		}

		// dfs를 위한 check배열
		check = new boolean[n];

		// 모든 정점을 확인한다.
		for (int i = 0; i < n; i++) {
			dfs(i, 1);
		}
		System.out.println(0);

	}

	private static void dfs(int n, int cnt) {
		if (cnt >= 5) {
			System.out.println(1);
			System.exit(0);
		}

		check[n] = true;
		for (int i : arr[n]) {
			if (!check[i])
				dfs(i, cnt + 1);
		}
		check[n] = false;
	}
}