[백준] 2644-촌수계산(C++)

문제링크:https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

처음에 보자마자 생각난건 union-find 알고리즘이였다. 서로 친척인지 확인을 해주기 위한 방법으로 사용하였다.

그이후에는 몇가지 케이스를 대입보면서 촌수계산을 분명하게 하기위해서는 완전탐색을 해야하는 것을 깨닭았고,

dfs와 bfs중에 고민하였다. 아마 dfs로도 풀이가 가능할 것이다. 탐색에 좀 더 적합한 bfs를 선택했다.

 

 

 

1. search_root() 함수를 통해서 서로 친척인지 확인 

2. 출발점x로부터 y까지 도달하는 과정에서 각 값들을 큐에 저장하며 해당 직계도를 탐색

3. bfs함수 호출이 끝난후 cnt[y]값을 출력 ( 전달받아 오면서 값이 +1씩 증가했으므로 촌수와 동일)

 

bfs에서 !visited[arr[i][1]] 의 조건은 최소의 촌수를 선택해야하기 때문입니다. 

 

 

정답코드입니다. 

 

#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };

void bfs() {

	int que[101] = { 0 };
	int started = 0, ended = 0;

	que[ended++] = x;

	while (started != ended) {
		int val = que[started++];
		visited[val] = 1;

		for (int i = 0; i < m; i++) {
			if (arr[i][0] == val && !visited[arr[i][1]]) {
				
				que[ended++] = arr[i][1];
				cnt[arr[i][1]] = cnt[val] + 1;
			}

			if (arr[i][1] == val && !visited[arr[i][0]]) {
				
				que[ended++] = arr[i][0];
				cnt[arr[i][0]] = cnt[val] + 1;
			}

		}


	}

}


void search_root() {

	root_x = x;
	root_y = y;

	while (1) {
		bool t = false, r = false;
		for (int i = 0; i < m; i++) {
			if (arr[i][1] == root_x) {
				t = true;
				root_x = arr[i][0];

			}
			if (arr[i][1] == root_y) {
				r = true;
				root_y = arr[i][0];
			}
		}
		if (t == false && r == false)
			break;
	}
}


int main() {
	cin >> n;
	cin >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0]>>arr[i][1];
	
	search_root();
	if (root_x != root_y) {
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << cnt[y] << endl;

}

 

움.. 그런데... 생각해보니 searchroot가 필요가 없죠? 어차피 탐색이 안되면 cnt[y]값을 0일 것이기 때문에 그때만 -1로 출력을 해주면 되기 때문입니다.

 

수정답안 입니다.

 

 

#include <iostream>
using namespace std;
int n = 0, m = 0, x, y,a,b;
int arr[101][2] = { 0 };
int root_x, root_y;
int cnt[101] = { 0 };
bool visited[101] = { 0 };

void bfs() {

	int que[101] = { 0 };
	int started = 0, ended = 0;

	que[ended++] = x;

	while (started != ended) {
		int val = que[started++];
		visited[val] = 1;

		for (int i = 0; i < m; i++) {
			if (arr[i][0] == val && !visited[arr[i][1]]) {
				
				que[ended++] = arr[i][1];
				cnt[arr[i][1]] = cnt[val] + 1;
			}

			if (arr[i][1] == val && !visited[arr[i][0]]) {
				
				que[ended++] = arr[i][0];
				cnt[arr[i][0]] = cnt[val] + 1;
			}

		}


	}

}

int main() {
	cin >> n;
	cin >> x >> y;
	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr[i][0]>>arr[i][1];
	
	
	
	bfs();
	if (cnt[y]==0) {
		cout << -1 << endl;
		return 0;
	}

	cout << cnt[y] << endl;
	return 0;
}

 

아이디어자체를 생각하는게 어려운 문제였습니다. 구현난이도는 굉장히 낮구요.