[백준] 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

BFS 코드

촌수를 찾는다는건 가장 짧은 거리를 찾는 것과 같다고 볼 수있으므로 BFS를 이용할 수있다.

if (map[abc][i] == 1 && arr[i] == 0)

arr배열을 통해 거리값들을 받으면서 지나오지않은 노드만 queue에 넣어준다.

#include<iostream>
#include <queue>
using namespace std;
int N, X, Y, M;
int map[101][101];
int arr[101];
void bfs(int start, int end) {
	queue<int> q;
	q.push(start);
	arr[start] = 1;
	
	while (!q.empty()) {
		int abc = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {//다음노드탐색
			if (map[abc][i] == 1 && arr[i] == 0) { //부모가 될수 있는가 + 이미 다녀온 노드 아닌경우 
				q.push(i);
				arr[i] = arr[abc] + 1;
			}
		}

	}
}
int main() {
	cin >> N >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}
	bfs(X, Y);

	if (arr[Y] != 0) {
		cout << arr[Y];
	}
	else cout << -1;




	return 0;
}

 

 

 

DFS 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, X, Y, M;
int map[101][101];
int visited[101];
bool flag;
int cnt;
void dfs(int p, int s,int level,int before) { //이전값 들고다니기 
	if (p == s) {
		flag = true;
		cnt = level;
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (map[p][i] == 1) {
			if (i == before) continue; 	//양방향 트리이므로 cycle을 방지하기위해 before

			dfs(i, s, level + 1,p);
		}

	}

}

int main() {
	cin >> N >> X >> Y >> M;

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;

	}


	dfs(X,Y,0,0);
	if (cnt == 0) cout << -1;
	else cout << cnt;


	return 0;
}