BOJ 13023 : ABCDE

문제

---

문제 풀어보기

 

 

풀이

---

 

 

문제를 이해하는데 좀 오래 걸렸네요...

 

 

이 문제는 A -> B -> C -> D 처럼

친구의 친구의 꼬리를 4번 무는 경우를 찾는 겁니다.

 

 

그래서 DFS 를 사용해서 깊이가 4가 되는 경우를 찾으면 됩니다.

 

 

코드

---

#include <iostream>
#include <vector>
#define max 2000
using namespace std;


bool check[max + 1];
vector<int> v[max + 1]; // max+1 개의 벡터 생성
int n, m;

void dfs(int st, int index) {

	check[st] = true;

	// 깊이가 4인경우 종료
	if (index == 4) {
		cout << 1 << '\n';
		exit(0);
	}

	// st 의 친구를 탐색
	for (int elements : v[st]) {
		if (check[elements]) continue;
		dfs(elements, index + 1);

	}
	// 깊이만을 확인하기 때문에
	// 왔던곳도 탐색 가능
	check[st] = false;

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		// 무방향 그래프
		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (int i = 0; i < n; i++) {
		dfs(i, 0);
	}

	cout << 0 << '\n';

	return 0;
}