[ 백준-13023번 / 그래프 ] ABCDE

1. 문제

---

ABCDE 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

5514

1543

997

27.610%

문제

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 4

예제 출력 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

 

 

 

 

2. 소스코드

---

#include <iostream>
#include <vector>

using namespace std;

vector <int> adjList[2000];
bool visited[2000];
bool ans;

void findAns(int i, int cnt) {

	if (cnt >= 5) return;

	for (int j = 0; j < adjList[i].size(); j++) {
		//adjList[i][j];
		int next = adjList[i][j];
		if (!visited[next]) {
			visited[next] = true;	
			cnt++;
			if (cnt >= 5) {
				ans = true;
				return;
			}
			findAns(next, cnt);
			visited[next] = false;
			cnt--;
		}
	}
	return;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;

		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}

	for (int i = 0; i < n; i++) {
		visited[i] = true;
		findAns(i, 1);
		visited[i] = false;
	}

	if (ans) cout << 1 << '\n';
	else cout << 0 << '\n';
	
	return 0;
}