[백준 - Java] 13023번 : ABCDE

문제

www.acmicpc.net/problem/13023

 

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. 문제 이해

나는 문제 이해가 되지 않아 몇 번의 실패를 반복했다.
틀렸습니다. 시간 초과까지 많은 실패를 겪었다^^... 그래서 정리한다.

다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

이 말이 무엇이냐!
일단 사람의 수는 5명 이상부터라는 것을 생각하고 2번 예제로 이해를 해보자!

5 5
0 1
1 2
2 3
3 0
1 4
예제의 관계를 정점과 간선으로 표현해보면 아래의 그림과 같다.

그리고 이 관계에서
0과 1은 친구이다.
1과 2는 친구이다.
2와 3은 친구이다.
1과 4는 친구이다.
0 - 3 - 2 - 1 - 4로 노드가 한 번에 이어진다.
즉 5명의 친구가 4가지의 친구 관계를 가지며 문제와 같은 친구 관계를 가지게 되어 '1' 출력

그리고 또 다른 3번 예제를 보자
6 5
0 1
0 2
0 3
0 4
0 5

예제 3번은 1 - 0 - 3으로 최대 3명의 친구 수와 2개의 친구 관계밖에 나오지 않아 '0' 출력!

이렇듯 5개의 이어진 노드를 찾아야 하고 이를 위해 DFS를 사용했다.
0부터 N-1번에서 시작하는 DFS 탐색을 각각 하고 depth가 5가 될 때 답을 저장하고 출력한다.

DFS 관련 포스트

 

여기서 주의해야 할 점
기존의 DFS 코드에서는 정점을 방문했을 때 이를 체크하는 boolean v 배열에서 해당 정점의 인덱스의 값을 방문했다는 의미로 true로 만들어주었다.
하지만 이런 식으로 구현한다면 예제 2번의 경우 DFS의 결과 0 - 1 - 2 - 3 - 4로 탐색을 할 때 depth는 최대 4까지 밖에 찾지 못한다.

예제 2번

왜냐하면 0 - 1 - 2 - 3 - 4로 DFS 탐색을 할 때 1 - 4의 경우 1 - 2를 갈 때 이미 1이 방문했다고 표시되어있기 때문에 depth = 5를 만족하지 못하고 재귀가 끝나면서 다시 재귀 호출을 하게 된다.
그래서 함수 맨 끝에 v[i] = false를 추가해 depth = 5의 경우까지 찾아야 한다.

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	private static int m;
	private static ArrayList<Integer>[] list;
	private static int ans = 0;
	private static boolean[] v;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		m = M;
		
		//DFS를 위한 인접리스트 구현하기
		list = new ArrayList[N];
		v = new boolean[N];
		for(int i = 0; i < N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			list[n1].add(n2);
			list[n2].add(n1);
		}
		
		//N-1까지의 모든 정점에서 DFS를 통해 확인
		for(int i = 0; i < N; i++) {
			if(ans == 0)
				dfs(i, 1);
		}
		
		bw.write(Integer.toString(ans));
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static void dfs(int start, int depth) {
		//System.out.println(start + " " + depth); //방문 정점과 깊이를 확인해보고 싶을 때 사용
		if(depth == 5) {
			ans = 1;
			return;
		}
		
		v[start] = true;
		for(int i : list[start]) {
			int next = i;
			if(!v[next]) {
				dfs(next, depth+1);
			}
		}
		v[start] = false;
	
	}
}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%2313023/src/Main.java

KwonMinha/BOJ