방과후
ALGORITHM NOTE약 2분

BOJ 1194 - 달이 차오른다, 가자.

그래서 왜 달이 차면 안되는건데

#algorithm#boj#gold#graph-theory#graph-traversal#bfs#bitmask#grid
아카이브로 돌아가기

문제 링크

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

  • 빈 칸: 언제나 이동할 수 있다. ('.')

  • 벽: 절대 이동할 수 없다. ('#')

  • 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')

  • 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')

  • 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')

  • 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

풀이

같은 칸에 도착하더라도 어떤 열쇠를 들고 있는지에 따라 다음에 갈 수 있는 곳이 달라지므로, 단순한 2차원 BFS로는 부족하다. 상태를 (x, y, keyMask)로 잡고, 현재 가진 열쇠 집합까지 함께 관리해야 한다.

코드에서는 dist[x][y][bit]를 사용해 각 상태의 최소 이동 횟수를 저장한다. 빈 칸과 출구는 그대로 이동할 수 있고, 열쇠 칸에 들어가면 비트마스크에 해당 키를 추가한다. 문 칸은 대응하는 열쇠 비트가 켜져 있을 때만 통과할 수 있다.

이렇게 3차원 BFS를 돌리면 어떤 상태에 처음 도착한 순간이 그 상태의 최단 거리다. 출구 '1'에 도착하면 그 거리 값을 바로 반환하고, 끝까지 도달하지 못하면 -1을 출력하면 된다.

코드

cpp
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
using namespace std;
 
int n, m;
pair<int, int> start;
char graph[50][50];
int dist[50][50][1 << 6];
 
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
struct Node {
	int x, y, bit;
};
 
bool isIn(int x, int y) {
	return x >= 0 && y >= 0 && x < n && y < m && graph[x][y] != '#';
}
 
int solve() {	
	queue<Node> q;
	q.push({start.first, start.second, 0});
	dist[start.first][start.second][0] = 0;
 
	while(!q.empty()) {
		Node cur = q.front();
		q.pop();
		
		int x = cur.x;
		int y = cur.y;
		int bit = cur.bit;
 
		if (graph[x][y] == '1')
			return dist[x][y][bit];
 
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			int nBit = bit;
 
			if (!isIn(nx, ny)) continue;
 
			if (graph[nx][ny] >= 'a' && graph[nx][ny] <= 'f') {
				nBit = bit | (1 << (graph[nx][ny] - 'a'));
			}
			else if (graph[nx][ny] >= 'A' && graph[nx][ny] <= 'F') {
				if (!(bit & (1 << (graph[nx][ny] - 'A')))) continue;
			}
			
			if (dist[nx][ny][nBit] == -1) {
				dist[nx][ny][nBit] = dist[x][y][bit] + 1;
				q.push({nx, ny, nBit});
			}
		}
	}
 
	return -1;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	cin >> n >> m;
	memset(dist, -1, sizeof(dist));
 
	for (int i = 0; i < n; i++) {
		string input;
		cin >> input;
		for (int j = 0; j < m; j++) {
			graph[i][j] = input[j];
			if (graph[i][j] == '0') start = make_pair(i, j);
		}
	}
 
	cout << solve() << '\n';
	return 0;
}

복잡도

  • 시간 복잡도: O(NM⋅26)O(NM \cdot 2^6)
  • 공간 복잡도: O(NM⋅26)O(NM \cdot 2^6)

마무리

미로 BFS에 열쇠 조건이 붙는 순간, 위치만이 아니라 소지 상태도 함께 봐야 한다. 비트마스크를 붙인 3차원 BFS로 바꾸면 문과 열쇠 규칙이 깔끔하게 처리된다.