백준 ABCDE C++

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. A->B->C->D->E 형식을 만족시키면 되므로, 깊이가 5가 되었을시에, return 하도록 설정해주었습니다.
2. DFS 를 돌도록 작성해주었으며, vector<vector< > > 형식으로 그래프를 표현해주었습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> arr;

bool findPath(vector<vector<int>> &arr, vector<int> &path)
{
	// return depth value
	if (path.size() == 5)
	{
		return true;
	}

	int tmp = path.back();
	for(auto c : arr[tmp]) 
		{
			if (find(begin(path), end(path), c) == path.end()) {
				path.push_back(c);
				if(findPath(arr, path)) return true;
				path.pop_back();
			}
		}
	return false;
}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	/*----------------- INPUT -------------------*/
	int  n, m;
	cin >> n >> m; 
	arr.reserve(n);
	for(int i = 0 ; i < n ; i++) 
		{
			arr[i].reserve(n);
		}

	while(m--)
		{
			int a, b;
			cin >> a >> b;
			arr[a].push_back(b);
			arr[b].push_back(a);
		}

	/*----------------- SOLVE -------------------*/
	vector<int> s;
	for(int i = 0 ; i < n ; i++) {
		if(arr[i].size() != 0) {
			s.push_back(i);
			if(findPath(arr, s)) {
				cout << 1 << endl;
				return 0;
			} 
			s.pop_back();
		}
	}
	cout << 0 << endl;
}