[BOJ 18128 // C++] 치삼이의 징검다리 건너기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18128번 문제인 치삼이의 징검다리 건너기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/18128 

18128번: 치삼이의 징검다리 건너기

문제의 상황은 각 돌을 노드로, 서로 이동할 수 있는 돌 사이의 관계를 양끝 돌 중 더 늦게 물이 도달하는 시간을 가중치로 갖는 에지로 하는 그래프로 모델링할 수 있다. 출발점에서 도착점까지 이동할 수 있게 되는 가장 빠른 시각을 kruskal 알고리즘과 같은 원리로 계산해내 문제를 해결하자.

 

위 구현에 필요한 "각 땅에 물이 도달하는 시간"은 주어지는 물 생성지들을 source들로 하는 multisource BFS를 이용해 계산해낼 수 있다.

 

아래는 제출한 소스코드이다.

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

int N, NN, M;
int waterT[1000][1000];
string board[1000];

int dr[4] = { 1, -1, 0, 0 };
int dc[4] = { 0, 0, 1, -1 };
queue<pair<int, int>> que;
void bfs() {
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= N || cc < 0 || cc >= N || waterT[rr][cc]) continue;
			waterT[rr][cc] = waterT[r][c] + 1;
			que.push(make_pair(rr, cc));
		}
	}
}

int dr2[4] = { 1,1,1,0 };
int dc2[4] = { -1,0,1,1 };
vector<pair<int, int>> edges[2002];
int arr[1000001];
int findf(int cur) {
	if (cur == arr[cur]) return cur;
	return arr[cur] = findf(arr[cur]);
}

int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M; NN = N * N;
	while (M--) {
		int r, c; cin >> r >> c; r--, c--;
		waterT[r][c] = 1, que.push(make_pair(r, c));
	}
	waterT[0][0] = waterT[N - 1][N - 1] = 1;

	for (int r = 0; r < N; r++) cin >> board[r];

	bfs();
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] == '0') continue;
			for (int i = 0; i < 4; i++) {
				int rr = r + dr2[i], cc = c + dc2[i];
				if (rr >= N || cc < 0 || cc >= N || board[rr][cc] == '0') continue;
				edges[max(waterT[r][c], waterT[rr][cc])].emplace_back(make_pair(r * N + c, rr * N + cc));
			}
		}
	}
	for (int i = 0; i < NN; i++) arr[i] = i;

	for (int i = 1; i < 2002; i++) {
		for (auto& p : edges[i]) {
			int x = p.first, y = p.second;
			x = findf(x), y = findf(y);
			arr[y] = x;
		}
		if (findf(0) == findf(NN - 1)) {
			ans = i;
			break;
		}
	}

	cout << ans - 1;
}