[백준/C++] 2644번: 촌수계산

코드는 간단하지만 나는 이해하는데 한참 걸린 것 같다.

 

1) 촌수는 결국 시작점에서 끝점으로 갈때까지 몇 개의 열을 거치느냐(depth)/거리가 있느냐를 따지는 문제와 같아진다.

2) map구성하기: 방향 역시 양방향 모두 같은 결론에 도달한다. 3->7을 가는 경로나 7->3을 가는 경로나 같은 결과를 낸다. 그러므로 map을 구성할 때 양방향 모두 똑같이 길을 만들어 주면 된다.

3) 또한 기존 2D map이 상하좌우로 이동할 수 있는 것과 달리 이 문제의 경우 한방향으로만 탐색을 진행해야 한다. 

 

시작점이 7이기 때문에 7번째 행부터 탐색하기 시작한다. 처음엔 (7,2)에 방문한다(방문:2로 표시함). 주의할 점은 (2,7)에도 방문했다고 체크를 해줘야 된다.(둘이 같은 관계이므로) 

 

 

그 다음엔 2번째 행으로 가서 또 모든 열을 탐색한다. (2,1)에 방문하고 (1,2)도 방문체크를 한다. 

 

 

(2,8),(2,9)도 방문한다.

 

 

이후 큐의 가장 처음에 있는 1번째 행으로 간다. (1,3)을 방문한다.

 

 

그다음 큐에 있는 8번째 행과 9번째 행은 모두 방문이 되어 있기 때문에 방문하지 않고 탐색을 끝낸다. 탐색은 똑같고 depth를 출력할 지, distance를 출력할 지에 따라 두가지 방향으로 코드를 짜보았다.

 

queue의 input으로 다음에 갈 열/ depth를 넣을 때 코드

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

int N, nCombi;
int Start, End;
int map[101][101];
int ans=-1;

void bfs(int x, int depth) {


	queue <pair<int,int>>  q;
	q.push(make_pair(x,depth));


	while (!q.empty()) {
		int cx = q.front().first;
		int depth = q.front().second;
		q.pop();

		if (cx == End) {
			ans = depth;
		}

		for (int i = 1; i <= N; i++) {
			if (map[cx][i] == 1) {

				map[cx][i] = 2;
				map[i][cx] = 2;
				q.push(make_pair(i,depth+1));
			}
		}

	}


}


int main() {

	cin >> N;
	cin >> Start >> End;
	cin >> nCombi;

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

	cout << ans;


	return 0;
}

 

각 사람마다 distance를 저장하는 배열을 둘 때, 코드

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

int N, nCombi;
int Start, End;
int map[101][101];
int dist[101];
void bfs(int x) {


	queue <int> q;
	q.push(x);
	while (!q.empty()) {
		int cx = q.front();
		q.pop();

		for (int i = 1; i <= N; i++) {
			if (map[cx][i] == 1) {

				map[cx][i] = 2;
				map[i][cx] = 2;
				dist[i] = dist[cx] + 1;
				q.push(i);
				
			}
		}

	}


}


int main() {

	cin >> N;
	cin >> Start >> End;
	cin >> nCombi;

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

	bfs(Start);

	if (dist[End] == 0) cout << "-1";
	else cout << dist[End];

	return 0;
}

 

DFS

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

int N;
int x, y;
int M;
int map[101][101];
int visit[101];
int ans = -1;

void dfs(int cx, int depth) {
	if (cx == y) {
		ans = depth;
		return;
	}
	for (int i = 1; i <= N; i++) {
		if (map[cx][i] == 1 && visit[i] == 0) {
			map[cx][i] == 2;
			map[i][cx] == 2;
			visit[i] = 1;
			dfs(i, depth + 1);
		}
	}
}

int main() {

	cin >> N;
	cin >> x >> y;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int tmp_x, tmp_y;
		cin >> tmp_x >> tmp_y;
		map[tmp_x][tmp_y] = 1;
		map[tmp_y][tmp_x] = 1;
	}


	dfs(x,0);
	cout << ans;

	return 0;
}