백준 13023 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을 출력한다.

---

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

int N, M;
vector<int> rel[2000];
bool check[2000];
int possible = 0;

void dfs(int start, int count)
{
	check[start] = true;//시작사람을 true
	if (count == 4)//서로다른 5명이 1자로 관계를 가진 상태면(총 4개의 관계) return
	{
		possible = 1;
		return;
	}
	for (int i = 0; i < rel[start].size(); i++)
	{
		if (check[rel[start][i]])//이미 체크된 사람이면 continue
			continue;
		dfs(rel[start][i], count + 1);//체크안된 사람을 시작점으로 재귀
	}
	check[start] = false;
	return;
}

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

	for (int i = 0; i < N; i++)//관계의 시작점이 누군지 모르므로 for문으로 다 돌려봄
	{
		dfs(i, 0);
		if (possible==1)
			break;
	}
	cout << possible;
}

---

1.vector의 push_back을 사용하여 사람1과 관련 있는 사람들은 모두 rel[사람1]에 집어 넣는다.

 

2.dfs 함수의 인자로 탐색 시작할 사람 (start)과 관계의 수(count)를 인자로 한다.

 

3. 사람 1부터 탐색을 해야 조건 관계가 나오는지, 사람 2부터 탐색을 해야 조건 관계가 나오는지 모르므로 for문을 통해 start값을 바꿔가며 dfs함수를 돌린다.

 

4.bool형 배열 check를 사용해 이미 체크한 사람이면 continue하고 체크 안한 사람만을 dfs의 start인자로 하여 

서로 다른 사람 5명이 4번의 관계를 잇는 조건을 구하도록 한다.

 

5.count==4 관계의 개수가 4가 되면 possible을 1로 하고 return한다.