[c++ 백준] (13023번) ABCDE

문제

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. DFS 를 이용하여 문제를 해결하였습니다.

2. 그래프를 연결하기 위해 Vector 배열을 선언한뒤 양방향 연결을 했습니다.

for (int i = 0; i < M; i++)
{
	cin >> a >> b;
	people[a].push_back(b);
	people[b].push_back(a);
}

3. DFS 이용하여 그래프를 접근해 친구 관계의 길이가 4인지를 확인합니다.

4. 친구 관계의 길이가 4일 경우 DFS 탐색을 종료 합니다.

---

코드

#include<iostream>
#include<vector>

#define endl "\n"
using namespace std;

vector<int> people[2001];
bool visit[2001];
bool answer = false;

void DFS(int length , int cur)
{
	if (length == 4)
	{
		answer = true;
		return;
	}
	for (auto i : people[cur])
	{
		if (!visit[i])
		{
			visit[i] = true;
			DFS(length + 1, i);
			visit[i] = false;
		}
	}
}

void Answer()
{
	int N, M;
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		people[a].push_back(b);
		people[b].push_back(a);
	}
	for (int i = 0; i < N; i++)
	{
		visit[i] = true;
		DFS(0, i);
		visit[i] = false;
		if (answer) break;
	}
	cout << answer;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}