[BOJ] 백준 2544번: 촌수계산 C++ : 아주정은

근무하면서 커밋 한번 하면 쉬는거 국룰이라길래 쉬면서 촌수계산이라는 문제를 풀었다.

이 문제들은 현정이가 만들어놓은 문제집에서 골라 푸는건데 그 문제집에 있는 100문제를 다 풀고싶다.

단순히 코테를 준비하는 것이 아니라 재밌다 ㅋㅋㅋ 취미가 문제풀이가 됐으면 좋겠다.

일단 촌수계산은 어릴때부터 많이해봐서 문제 자체는 어렵지 않았다. 그래프를 그릴수만있다면

진짜 한조각 케익이라고 생각했다. 막상 그래프를 그리고 어떻게 돌아야 효율적일까 하는 고민을 하게되었다.

나는 queue를 이용해서 BFS방식을 사용하였다.

촌수를 계산할 두명중 한명을 큐에 넣어주고 그 한사람과 연결된 모든 사람을 큐에 집어넣는다.

그리고 방문했다는 표시를 해준다. 그렇게 그래프를 돌다가 찾는 사람을 발견하면 관계를 출력해주면 된다.

한 계층씩 내려갈때마다 time을 늘려줌으로써 몇 촌인지 계산한다.

싸이월드에서는 너와 나는 1촌이었는데, 지금 우리는 몇촌일까?

삼시세끼 어촌편 보러가야짓,, 쵼쵼!

#include <iostream>
#include <queue>

using namespace std;

struct Que {
	int x;
	int time;
};

int board[102][102];
bool vis[102];

void initialize() {
	for (int i = 0; i < 102; i++) {
		vis[i] = false;
		for (int j = 0; j < 102; j++) {
			board[i][j] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; //사람 수
	int a, b; // 촌수계산 두사람
	int m;
	int x, y;
	int relation = -1;
	cin >> n >> a >> b >> m;

	initialize();

	while (m--) {
		cin >> x >> y;
		int i = 0;
		while (board[x][i] != 0) {
			i++;
		}
		board[x][i] = y;

		int j = 0;
		while (board[y][j] != 0) {
			j++;
		}
		board[y][j] = x;
	} // 그래프 형성
	
	queue<Que> Q;
	Q.push({ a,0 });
	vis[a] = true;
	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();
		int i = 0;
		while (board[cur.x][i] != 0) {
			int neighbor = board[cur.x][i];
			if (neighbor == b) {
				relation = cur.time + 1;
				goto ijsilver;
			}
			if (vis[neighbor] == false) {
				Q.push({ board[cur.x][i],cur.time + 1 });
				vis[board[cur.x][i]] = true;
			}
			i++;
		}
	}

ijsilver:
	cout << relation << endl;
	return 0;
}

//양방향 간선을 통해서 그래프를 그리자.