[G5] 백준 13023번 ABCDE C++ 깊이 우선 탐색

리뷰

 

https://www.acmicpc.net/problem/13023

N이 2000이라 가지치기가 필요할 것이라 생각했는데 그냥 제출해도 되는 문제였다.

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 사람의 수를 저장할 변수
• m : 친구 관계의 수를 저장할 변수
• ans : 정답 여부를 저장할 변수
• v : 방문 정보를 저장할 배열
• edges : 인접 리스트를 저장할 배열

 

함수

1. dfs

void dfs(int level, int node)

 

깊이 우선 탐색을 통해 연속된 5명의 친구 관계가 있는지 체크하는 함수

• 매개 변수로 재귀 단계 level과 현재 노드 번호 node를 전달 받는다.
• 기저 조건으로 재귀 단계가 5가 될 경우 ans를 true로 변환 후 return 처리한다.
• node의 인접 리스트를 순회하며 방문 된 번호가 아닐 경우 방문 처리 후 재귀 단계를 올려 재귀를 진행한다.
• 재귀를 마친 후에 빠져나오며 방문 처리를 해제해 준다.

 

문제풀이

1. n, m값을 입력 받고, m개의 간선 정보를 입력 받아 인접 리스트 edges에 양방향 간선으로 추가해 준다.
2. 0~n - 1번을 순회하며 방문 처리 후 dfs함수에 초기 재귀 레벨 1과 노드 번호 i를 전달하여 재귀를 수행한다.
3. 재귀를 빠져나온 후 ans가 true일 경우 1을 출력하고 리턴해 준다.
4. 만약 탐색이 종료된 후에도 ans가 false라면 0을 출력해 준다.

 

트러블 슈팅

1. 가지치기를 위해 재귀 레벨 5까지 도달하지 못한 경우 해당 경로의 친구들은 dfs를 수행하지 않게 해주었다.
2. 하지만 위 방법은 모든 상태를 체크할 수 없는 듯 하여 제거해 주니 AC를 받았다.

 

참고 사항

• 대충 계산해 보니 재귀 단계가 최대 5이므로 최악의 케이스에도 2000 * 2^5 정도로 처리가 가능해 보인다.

 

정답 코드

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

const int N = 2000;
int n, m;
bool ans;
bool v[N];
vector<int> edges[N];

void dfs(int level, int node) {
	if (level == 5) {
		ans = true;
		return;
	}

	for (int i : edges[node]) {
		if (v[i]) continue;
		v[i] = true;
		dfs(level + 1, i);
		v[i] = false;
	}
}

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

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

	for (int i = 0; i < n; ++i) {
		v[i] = true;
		dfs(1, i);
		v[i] = false;
		if (ans) {
			cout << 1;
			return 0;
		}
	}

	cout << 0;
}