[백준] 13023 ABCDE (복습완료)>>재귀 DFS

 

문제

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<bits/stdc++.h>

using namespace std;
int visited[2001];
int n, m, a, b, cnt, ans = 0;
vector<vector<int>>vt(2000,vector<int>());

void dfs(int k) {
	if (ans == 1)return; //탈출조건

	if (cnt == 4) { //기저: 깊이가 4
		ans = 1;
		return;
	}
	visited[k] = 1;
	for (int i = 0; i < vt[k].size(); i++) {
		if (!visited[vt[k][i]]) {
			cnt++;
			dfs(vt[k][i]);
		}
	}
	visited[k]=0; //가지치기
	cnt--;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	memset(visited, 0, sizeof(visited));
	for (int i = 0; i < m; i++) { //2000*2000 array가 아닌 인접 array list로 구현하면 시간을 절약할 수 있습니다.
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		if (ans == 1) {
			cout << 1;
			return 0;
		}
		cnt = 0;
		dfs(i);
	}
	cout << 0;
	return 0;
}

골드5 DFS문제입니다.

DFS를 이용해 깊이가 4이하의 모든 경우의 수를 찾아야합니다.

깊이가 4가 되는경우 재귀를 탈출해야합니다.

가지치기를 해야하므로 재귀가 끝나는 경우 미방문처리를 해야합니다.

-------------------------------------------------------------------------------------------------------------------------------------------------------------

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

vector<int>vt[2001];
int v[2001];
int n, m, ans;
void rec(int k,int d) {
	if (ans)return;
	if (d == 4) {
		ans = 1; return;
	}
	v[k] = 1;
	for (int p : vt[k])  //for문 이렇게 사용하면 편하다
		if (!v[p])rec(p,d+1);
	v[k] = 0; //가지치기
}
int main() {
	int a, b;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		vt[a].push_back(b);
		vt[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		if (ans) { cout << 1; return 0; }
		rec(i, 0);
	}
	cout << 0;
}