[백준] 촌수계산

// BFS 버전
#include <iostream>
#include <queue>

using namespace std;

#define MAX 101

int map[MAX][MAX];
bool visited[MAX];
queue<int> que;


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

	int N, num1, num2, M;

	cin >> N >> num1 >> num2 >> M;

	// N은 정점의 개수, num1은 시작정점, num2는 도착정점, M은 간선의 개수
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}

	que.push(num1);
	visited[num1] = true;

	int cnt = 0;

	while (!que.empty()) {
		// BFS
		int size = que.size();
		// 큐의 사이즈만큼 반복
		for (int i = 0; i < size; i++) {
			int cur = que.front();
			que.pop();
			// 현재 정점이 num2와 같다면 cnt를 출력하고 종료
			if (cur == num2) {
				cout << cnt;
				return 0;
			}
			// 현재 정점과 연결된 정점들을 모두 탐색
			for (int j = 1; j <= N; j++) {
				if (map[cur][j] == 1 && !visited[j]) {
					que.push(j);
					visited[j] = true;
				}
			}
		}
		// 한 레벨을 다 탐색했으므로 cnt를 증가시킨다.
		cnt++;
	}

	if (!visited[num2]) {
		cout << -1;
		return 0;
	}

	return 0;
}

// DFS 버전
#include <iostream>

using namespace std;  

#define MAX 101  

int map[MAX][MAX];  
bool visited[MAX];  
int result = -1;  

void dfs(int cur, int target, int cnt, int N) {  
	// cur: 현재 정점, target: 도착 정점, cnt: 현재까지의 경로 길이, N: 정점의 개수
   if (cur == target) {  
       result = cnt;  
       return;  
   }  

   visited[cur] = true;  

   // 인접한 정점 탐색
   for (int i = 1; i <= N; i++) {  
       if (map[cur][i] == 1 && !visited[i]) {  
           dfs(i, target, cnt + 1, N);  
       }  
   }  
}  

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

   int N, num1, num2, M;  

   cin >> N >> num1 >> num2 >> M;  

   // N은 정점의 개수, num1은 시작정점, num2는 도착정점, M은 간선의 개수  
   for (int i = 0; i < M; i++) {  
       int a, b;  
       cin >> a >> b;  
       map[a][b] = 1;  
       map[b][a] = 1;  
   }  

   dfs(num1, num2, 0, N);  

   cout << result;  

   return 0;  
}