취미로 코딩하기

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

이번에 볼 문제는 백준 25307번 문제인 시루의 백화점 구경이다.
문제는 아래 링크를 확인하자.

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

먼저, 시루가 접근할 수 없는 칸이 어디어디인지를 모두 알고 있다면 이 문제는 단순한 bfs문제와 같은 방식으로 해결할 수 있게 된다. 시루가 접근할 수 없는 칸은 1) 벽이거나 2) 택시거리가 K 이하인 칸에 마네킹이 존재하는 칸이다.

각 마네킹마다 택시거리가 K 이하인 점을 한번씩 조사한다면 최악의 경우(거의 모든 칸에 마네킹이 들어서있고 K의 값이 큰 경우) 상당히 많은 계산량이 필요해지므로 효율적으로 2)의 경우를 해결할 필요가 있다. 이는 각 마네킹의 위치들을 source로 하는 multisource bfs를 구현하는 것으로 해결이 가능하다.

택시거리를 생각할 때 벽 등이 있는지와 상관없이 오로지 좌표의 값만으로 계산한다는 점에 유의하자. 즉, 마네킹으로 인해 접근할 수 있는 칸을 조사할 때 벽 등을 무시하고 bfs를 진행해야 하는 점에 유의하자.

아래와 같이 dr 배열과 dc 배열을 이용하면 이와 같은 문제에서의 bfs 구현을 편하게 할 수 있다.

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

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

int R, C, K;
int sr, sc;
int arr[2000][2000];
queue<pair<int, int>> que1;
queue<pair<int, int>> que2;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

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

	cin >> R >> C >> K;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			int& cur = arr[r][c];
			cin >> cur;
			if (cur == 3) que1.push(make_pair(r, c));
			else if (cur == 4) cur = 1, sr = r, sc = c;
		}
	}

	while (K--) {
		int quecnt = que1.size();
		while (quecnt--) {
			int r = que1.front().first, c = que1.front().second; que1.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (arr[rr][cc] == 3) continue;
				arr[rr][cc] = 3;
				que1.push(make_pair(rr, cc));
			}
		}
	}

	int ans = 0;
	que2.push(make_pair(sr, sc));
	while (1) {
		ans++;
		int quecnt = que2.size();
		if (quecnt == 0) {
			cout << -1;
			return 0;
		}
		while (quecnt--) {
			int r = que2.front().first, c = que2.front().second; que2.pop();
			for (int i = 0; i < 4; i++) {
				int rr = r + dr[i], cc = c + dc[i];
				if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
				if (arr[rr][cc] == 1 || arr[rr][cc] == 3) continue;
				else if (arr[rr][cc] == 2) {
					cout << ans;
					return 0;
				}
				arr[rr][cc] = 3;
				que2.push(make_pair(rr, cc));
			}
		}
	}
}