BOJ 9376 - Jailbreak(탈옥)

* BOJ 9376 - Jailbreak(탈옥)

  (https://www.acmicpc.net/problem/9376)

 

  nextq에 대한 다른 방식이 있어서 기억하고자 포스팅하고자 한당

  

  문제는 그다지 어렵진 않다. 문제를 다소 변경해보자. 밖에서 문을 열어 주는 과정, 죄수1이 여는 과정, 죄수2가 여는 과정으로 문제를 분할하고, 세 사람이 한 점에서 모인다고 생각해보자. 세 사람이 그 한 점에 최소한의 문을 열고 오게끔 구성을 한다면 답을 충분히 도출할 수 있다. 주어진 지도 안에서 만나는 경우가 없을 수도 있으므로, 바깥 테두리를 설정해주면 된다.

  보통 나는 이런 step by step bfs(내가 임의로 지은 이름임) 문제는 q와 nextq를 두어 문제를 해결하지만, solution에 다른 방식으로 해결하더라.. ㅎㅎ 좀 더 깔끔한 것 같아서 소개해주고자 한다.

* toggle queue

  1. queue를 크기가 2인 배열로 선언한다.

  2. 초기엔 0 인덱스에 출발점을 지정한다.

  3. 분기를 시켜야할 이벤트가 발생하면(여기서는 문('#')을 만나면), 다른 queue에 값을 대입한다.

  4. 현재 queue가 비었다면 다른 queue로 이동한다(toggle).

  5. 둘 다 비어있다면 종료.

- 코드

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
char board[102][103];
struct _d { int y, x; };
int N,M,dy[] = { 0,0,-1,1 }, dx[] = { 1,-1,0,0 };
void bfs(_d src, int dp[102][103]) {
	int ret = 1e9,i,c,d=0;
	memset(dp, -1, 102*103*sizeof(int));
	queue<_d> q[2];
	q[c = 0].push(src);
	dp[src.y][src.x] = 0;
	while (!q[0].empty() || !q[1].empty()) {
		if (q[c].empty()) { // if current queue has been over, toggle queue.
			d++;
			c = !c;
		}
		_d u = q[c].front(); q[c].pop();
		for (i = 0; i < 4; i++) {
			int ty = u.y + dy[i], tx = u.x + dx[i];
			if (0 <= ty && ty <= N + 1 && 0 <= tx && tx <= M + 1 && board[ty][tx] != '*' && dp[ty][tx] == -1) {
				dp[ty][tx] = d;
				q[(board[ty][tx] == '#' ? !c : c)].push({ ty,tx });  // if event has occurred, push to other queue.
			}
		}
	}
}

int main() {
	int T, i, j, ans,am,bm,toB, outer[102][103], as[102][103], bs[102][103];
	_d a, b;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d\n", &N, &M);
		memset(board, '.', sizeof board);
		a.y = -1;
		for (i = 1; i <= N; i++) {
			scanf("%s", board[i]+1);
			for (j = 1; j <=M; j++)
				if (board[i][j] == '$') {
					if (a.y == -1) a = _d{ i,j };
					else b = _d{ i,j };
				}
		}
		bfs({ 0,0 }, outer);
		bfs(a, as);
		bfs(b, bs);
		ans = outer[0][0]+as[0][0]+bs[0][0];
		for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) {
			if (outer[i][j] < 0) continue;
			ans = min_v(ans, (board[i][j] == '#') + outer[i][j] + as[i][j] + bs[i][j]);
		}
		
		printf("%d\n", ans);
	}
	return 0;
}