[DFS, 난이도 중] 백준 1389번 케빈 베이컨의 6단계 법칙

이 문제는 BFS로 푸는게 훨씬 간단하다.

왜냐하면 최단경로를 구해야 하는 문제이기 때문이다.

 

DFS로 하면 꽤 신경써야될 것들이 있다. 깊이 매개변수를 추가해줘야하고 DFS를 다 돌면 방문처리를 해제해야한다.

본인은 DFS연습 차원으로 DFS로 풀었기 때문에 DFS이용 기준으로 난이도를 중으로 정했다.

BFS로 풀었다면 중하~하 사이가 아닐까 싶다.

 

주어진 예제를 양방향 그래프로 도식화한 그림이다.

dfs의 매개변수는 각각 (출발점,도착점,깊이) 이다.

출발점=도착점인 경우 깊이의 최솟값을 갱신하는 처리를 해준뒤 하나의 dfs함수를 종료한다.

노드n이 노드1~n까지 모두 탐색하여 구한 최단경로의 합은 kevin[n] 이다.

kevin의 최솟값을 가지는 최초의 인덱스값을 출력하면 문제는 해결된다.

 

BFS대신 DFS로 최단경로를 구할 시 처리해야될 것들

1. DFS를 끝내고 빠져나온 노드의 방문여부를 false로 바꿔준다.

2. 매개변수에 깊이를 나타내는 변수를 추가한다.

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
bool visited[101];
vector<int> a[101];
int kevin[101];
int ans;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n,m;
int mini(int x, int y) {
	if (x < y) return x;
	else return y;
}
void dfs(int x, int d, int depth) {
	if (x == d) {
		ans = mini(ans, depth);
		return;
	}
	visited[x] = true;
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (!visited[y]) {
			dfs(y, d, depth + 1);
			visited[y] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	int answer = 101;
	for (int i = 1; i < m+1; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i < n+1; i++) {
		for (int j = 1; j < n + 1; j++) {
			memset(visited, false, sizeof(visited));
			ans = 101;
			dfs(i, j, 0);
			kevin[i] += ans;
		}
		answer = mini(answer, kevin[i]);
	}
	for (int i = 1; i < n + 1; i++) {
		if (kevin[i] == answer) {
			cout << i;
			return 0;
		}
	}
}