[Algorithm][C++] BOJ 9376 탈옥

url: https://www.acmicpc.net/problem/9376

9376번: 탈옥

 

 

풀이 핵심

1. BFS 활용

2. 상근이가 외부에서 접근하는 경우, 죄수1&2가 내부에서 나가는 경우 3가지 경우 모두 탐색하여 각각의 벽을 만난 횟수를 기록한다.

3. deque 또는 우선 순위 큐를 이용해 벽일 경우 벽이 아닐 경우를 구분해 큐에 push 한다. (벽을 만나지 않은 경우가 우선적으로 탐색될 수 있도록)

4. 3가지 경우를 모두 합한다. (이 때 벽에서는 중복을 제거해준다)

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <deque>
using namespace std;

int tc, R, C;
char map[100 + 2][100 + 2];
int check[100 + 2][100 + 2][3];
int sum[100 + 2][100 + 2];

struct INFO { int r, c, cnt; };
INFO start[2];
int start_idx;

void bfs(int r, int c, int idx) {
	deque<INFO> q;
	q.push_front({ r,c,0 });
	check[r][c][idx] = 0;
	while (!q.empty()) {
		INFO cur = q.front();
		q.pop_front();
		int const dr[] = { 1,-1,0,0 };
		int const dc[] = { 0,0,1,-1 };

		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr > R + 1 || nc < 0 || nc > C + 1) continue;
			if (check[nr][nc][idx] != -1) continue;
			if (map[nr][nc] == 0 || map[nr][nc] == '$' || map[nr][nc] == '.') {
				q.push_front({ nr,nc,cur.cnt });
				check[nr][nc][idx] = cur.cnt;
			}
			else if (map[nr][nc] == '#') {
				q.push_back({ nr,nc,cur.cnt + 1 });
				check[nr][nc][idx] = cur.cnt + 1;
			}
		}
	}
}

int main() {
	scanf("%d", &tc);
	for (int i = 0; i < tc; i++) {
		int ans = 100 * 100;
		memset(map, 0, sizeof(map));
		memset(check, -1, sizeof(check));
		memset(sum, 0, sizeof(sum));
		start_idx = 0;
		scanf("%d %d", &R, &C);
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				scanf(" %c", &map[i][j]);
				if (map[i][j] == '$') start[start_idx].r = i, start[start_idx++].c = j;
			}
		}
		bfs(0, 0, 0);
		bfs(start[0].r, start[0].c, 1);
		bfs(start[1].r, start[1].c, 2);

		for (int i = 0; i <= R + 1; i++) {
			for (int j = 0; j <= C + 1; j++) {
				if (map[i][j] == '#') sum[i][j] -= 2;
				for (int k = 0; k < 3; k++) sum[i][j] += check[i][j][k];
				if (sum[i][j] != -3 && sum[i][j] < ans) ans = sum[i][j];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

아쉬운점

솔직히 조금 어려웠다. (다른 사람들의 풀이를 보고 구현할 수 있었다)

3가지 경우를 모두 생각해야 한다는 점이 이해가 잘 되지 않는다.