[DFS] 백준 13023 - ABCDE

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

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 

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

 

---

처음에 문제가 헷갈려서 좀 헤맸다. A - B - C - D - E 같은 친구관계가 N명 만큼 이어져있어야 한다고 생각했었다.. 그래서 계속 틀린 답이 나왔다.

알고보니 그냥 5명의 친구관계가 A - B - C - D - E 처럼 이어져있기만 하면 됐다. dfs로 쉽게 풀 수 있었다.

 

• 사람의 수가 최대 2000명까지 될 수 있다. dfs에서 매번 a와 친구인 사람을 찾는다면 시간초과가 걸릴 것이다.

처음에는 map으로 key를 a, 값을 a의 친구들 배열로 저장하는걸 생각했다.

그러나 map은 저장할 때마다 정렬을 하기 때문에 느려질 수밖에 없다. vector 2차원 배열로 대신하기로 했다.

삽입마다 매번 정렬을 하지도 않고, 인덱스만 알면 시간복잡도가 O(1)이기 때문에 저장과 탐색에서 많은 시간이 소모되지 않을 것이다.

• 친구 관계가 4번만 이어진다면 1을 출력한다.

dfs의 깊이가 4가 된다면 조건에 만족한다.

 

#include <iostream>
#include <vector>

#define endl '\n'
#define GOAL 4

using namespace std;

int N, M; // 사람의 수, 친구관계의 수
vector<int> relation[2001]; // 친구 관계
bool visited[2001]; // 방문여부 체크

void dfs(int index, int cnt) // 벡터의 인덱스, 깊이 수
{
	if (cnt >= GOAL)
	{
		cout << 1 << endl;
		exit(0);
	}
	for (int i = 0; i < relation[index].size(); ++i) // index의 친구 수만큼 검색
	{
		if (!visited[relation[index][i]]) // 아직 방문한 적 없는 친구
		{
			visited[relation[index][i]] = true;
			dfs(relation[index][i], cnt + 1); // 친구 검색
			visited[relation[index][i]] = false;
		}
	}
}
int main()
{
	cin >> N >> M;

	for (int i = 0; i < M; ++i)
	{
		int f1, f2;
		cin >> f1 >> f2;

		relation[f1].push_back(f2);
		relation[f2].push_back(f1);
	}

	for (int i = 0; i < N; ++i)
	{
		visited[i] = true;
		dfs(i, 0); // 출발하는 곳이 바뀌도록
		visited[i] = false;
	}

	cout << 0 << endl;
}