BOJ - 9376번 탈옥(C++)

문제 출처: https://www.acmicpc.net/problem/9376

문제 난이도

Platinum 5

문제 접근법

bfs가 아닌 deque을 이용해야 한다.
그리고 경우는 3가지로 나눈다.
1) $ 죄수가 밖으로 나갈 때, 두 가지
2) 밖에 있는 상근이가 문을 열고 들어오는 경우
이렇게 3번을 check할 경우 문을 세명이 3번 열게 되는 거니깐 -2를 해줘서 한번만 열어주는 경우로 봐야한다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#define INF 987654321

using namespace std;

int dist[103][103][3];
bool ch[103][103][3];
int dy[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
vector<string> arr;

void checkDoor(int x, int y, int H, int W,int type) {
	deque<pair<int, int>> dq;
	dq.push_front({ x,y });
	ch[x][y][type] = true;
	while (!dq.empty()) {
		x = dq.front().first;
		y = dq.front().second;
		dq.pop_front();
		for (int k = 0; k < 4; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			if (nx < 0 || ny < 0 || nx >= H + 2 || ny >= W + 2 || ch[nx][ny][type] || arr[nx][ny] == '*') continue;
			ch[nx][ny][type] = true;
			if (arr[nx][ny] == '.' || arr[nx][ny] == '$') {
				dist[nx][ny][type] = dist[x][y][type];
				dq.push_front({ nx,ny });
			}
			else if (arr[nx][ny] == '#') {
				dist[nx][ny][type] = dist[x][y][type] + 1;
				dq.push_back({ nx,ny });
			}
		}
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(dist, 0, sizeof(dist));
		memset(ch, false, sizeof(ch));
		int h, w;
		cin >> h >> w;
		string str = "";
		pair<int, int> p[2];
		int idx = 0;
		for (int i =0; i < w+2; i++) {
			str += ".";
		}
		arr.push_back(str);
		for (int i = 0; i < h; i++) {
			cin >> str;
			str = "." + str;
			str += ".";
			arr.push_back(str);
		}
		str = "";
		for (int i = 0; i < w+2; i++) {
			str += ".";
		}
		arr.push_back(str);
		for (int i = 1; i < h + 1; i++) {
			for (int j = 1; j < w + 1; j++) {
				if (arr[i][j] == '$') p[idx++] = { i,j };
			}
		}
		checkDoor(0, 0, h, w, 0);
		checkDoor(p[0].first, p[0].second, h, w, 1);
		checkDoor(p[1].first, p[1].second, h, w, 2);
		int res = INF;
		for (int i = 0; i < h+2; i++) {
			for (int j = 0; j < w + 2; j++) {
				if (arr[i][j] == '*') continue;
				int sum = 0;
				for (int k = 0; k < 3; k++) {
					sum += dist[i][j][k];
				}
				if (arr[i][j] == '#') sum -= 2;
				res = min(sum, res);
			}
		}
		cout << res << "\n";
		arr.clear();
	}
	return 0;
}

피드백

푸는데 진짜 오래 걸렸다. 심지어 bfs로 하다가 한계에 봉착해서 검색하니깐 deque을 이용하라는 걸 보고 다시 풀었다. 진짜 deque을 이용할 생각을 어떻게 한걸까 뚫려있는 길을 먼저 뚫고 나서 문을 여는 경우를 따지는 거다.