[BOJ] #13023 _ ABCDE

[ABCDE] https://www.acmicpc.net/problem/13023

13023번: ABCDE

처음에는 문제를 이해하기 어려웠다.

 

문제를 해석하면,

그냥 ABCDE가 친구이면 된다 == 5명이상이 친구이면 1, 아니면 0을 출력한다.

 

좀 더 이해하기 쉽게 예제를 가지고 풀이해보자면,

 

[예제 2번]

다음과 같은 입력은 아래의 그래프와 같이 관계를 표현할 수 있다.

 

해당 그래프에서 친구를 맺을 수 있는 관계의 수는 4이고, 5명이 친구를 맺을 수 있다.

왜냐하면, 아래의 그래프와 같이 한번에 이어질 수 있는 노드의 갯수가 5개이다.

0 - 3 - 2 - 1 - 4

 

개인적으로 문제를 이해하는데 어려움을 주었던 예제 3번으로도 확인해보면,

 

[예제 3번]

입력 값의 관계는 아래와 같은 그래프로 표현할 수 있다.

 

해당 그래프는 어떻게 이어보려고 해도 최대의 친구 수는 3명이다.

1 - 0 - 3

 

따라서, 0이 출력된다.

 

결과적으로, 노드는 한번만 거치고 이어지는 갯수가 5이면, 1을 출력하고 아니면 0을 출력하면 된다.

해당 문제를 풀기위해 DFS를 사용하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>

int relation[2000][2000] = { 0, };
int idx_count[2000] = { 0, };
int dfs(int idx, int check[], int count);
int main() {
	int n, m, a, b;
	int check[2000] = { 0, };

	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) { //Input data
		scanf("%d %d", &a, &b);
		relation[a][idx_count[a]++] = b;
		relation[b][idx_count[b]++] = a;
	}

	for (int i = 0; i < n; i++) { //Use DFS and Print result
		if (dfs(i, check, 0)) {
			printf("1");
			return 0;
		}
	}
	printf("0");

	return 0;
}

int dfs(int idx, int check[], int count) {
	check[idx] = 1;
	for (int i = 0; i < idx_count[idx]; i++) {
		if (check[relation[idx][i]] != 1) {
			if (count + 1 == 4) return 1;
			if (dfs(relation[idx][i], check, count + 1)) return 1;
		}
	}
	check[idx] = 0;
	return 0;
}