알고리즘 :: 백준 :: DFS :: 13023 :: ABCDE

문제

A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

문제접근

• $A - B-C-D$ 관계를 만족하는 간선이 그래프에 존재하는지 찾는 간단한 DFS 문제다.
• 임의의 시작점을 정하고 DFS를 수행하고 깊이가 4만큼 들어가는 관계가 있는지 찾는다.
• 절대로 인접행렬로 이 문제를 풀지 말자. AC를 받을 수 없다!!

코드

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N, M;
bool flag, visited[2000];
vector<int> human[2000];

void dfs(int here, int cnt) {
	if (cnt == 4) { flag = true; return; }

	visited[here] = true;
	for (int there = 0; there < human[here].size(); ++there)
		if (!visited[human[here][there]])
			dfs(human[here][there], cnt + 1);
	visited[here] = false;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;
	for(int i = 0; i < M; ++i) {
		int start = 0, end = 0;
		cin >> start >> end;
		human[start].push_back(end);
		human[end].push_back(start);
	}
	for (int i = 0; i < N; ++i) {
		dfs(i, 0);
		if (flag) break;
		memset(visited, false, sizeof(visited));
	}
	if (flag) cout << "1\n";
	else cout << "0\n";
}

• 임의의 시작점마다 새롭게 DFS를 시작하기 위해 memset() 함수를 사용.
• 매 DFS 마다 cnt변수를 하나씩 증가시켜서 4인 관계가 존재할 때 결과를 반환한다.

결과