[백준] 1194번: 달이 차오른다, 가자.

문제

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

설명

 전형적인 BFS 문제이나, 고려할 점이 많다. 미로에는 벽이 존재하며, 이 곳에는 이동할 수 없다. 추가로 열쇠와 문도 존재하는데, 열쇠는 소문자, 문은 대문자로 표시된다. 열쇠와 대응하는 문에 도달하면 지나갈 수 있다. 예를 들어 'a'를 가지고 있으면 'A'로 이동할 수 있다. 열쇠는 'a'부터 'f'까지 존재하며, 문 또한 'A'부터 'F'까지 존재한다. 시작 좌표는 0, 도착 좌표는 1로 표시된다. 1은 최소 한 개 존재하며, 여러 개 존재할 수 있다.

 visited 배열에 이동 횟수까지 기록하여 구현할 예정이다. 단순히 이차원 배열로 visited를 선언해도 될까? 그렇지 않다. 열쇠를 얻기 위해 중복 좌표를 방문해야 할 필요가 있을 수 있기 때문이다.(예제 입력 1 참고) 따라서 열쇠 보유 여부까지 visited에서 관리해야 한다. 비트마스킹을 사용하여 삼차원 visited 배열을 사용한다. 예를 들어 visited[3][4][45]에   a, c, d, f 열쇠를 가지고 있고 3행 4열에 위치할 때 이동 횟수가 저장된다.

코드

#include <iostream>
#include <queue>
#include <tuple>
#include <string>
#include <algorithm>
 
using namespace std;
 
char board[51][51];
int visited[51][51][(1 << 6)];
int n, m;
 
bool OutofBound(int x, int y) {
	return x < 0 || y < 0 || x >= n || y >= m;
}
 
int main() {
	cin >> n >> m;
 
	int sx, sy; // 시작 좌표
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
 
			if (board[i][j] == '0') {
				sx = i;
				sy = j;
			}
		}
	}
 
	queue<tuple<int, int, int>> q;
	q.push({ sx,sy,0 });
	visited[sx][sy][0] = 1;
 
	int dx[4] = { -1,0,1,0 };
	int dy[4] = { 0,1,0,-1 };
 
	int ans = -1;
	while (!q.empty()) {
		int x, y, keys;
		tie(x, y, keys) = q.front();
		int cnt = visited[x][y][keys];
		q.pop();
 
		if (board[x][y] == '1') {
			ans = cnt - 1;
			break;
		}
 
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
 
			// 방문하지 않았고 벽이 아닌 경우
			if (!OutofBound(nx, ny) && board[nx][ny] != '#' && !visited[nx][ny][keys]) {
				// 빈 칸이거나 출발지거나 도착지
				if (board[nx][ny] == '.' || board[nx][ny] == '0' || board[nx][ny] == '1') {
					visited[nx][ny][keys] = cnt + 1;
					q.push({ nx,ny,keys });
				}
				// 열쇠
				else if (board[nx][ny] >= 'a' && board[nx][ny] <= 'f') {
					int key_number = board[nx][ny] - 'a';
 
					int newKeys = keys | (1 << key_number);
					if (!visited[nx][ny][newKeys]) {
						visited[nx][ny][newKeys] = cnt + 1;
						q.push({ nx,ny,newKeys });
					}
				}
				// 문
				else if (board[nx][ny] >= 'A' && board[nx][ny] <= 'F') {
					char door = board[nx][ny];
					char key = tolower(door);
					int key_number = key - 'a';
 
					// 열쇠를 가지고 있다면
					if (keys & (1 << key_number)) {
						visited[nx][ny][keys] = cnt + 1;
						q.push({ nx,ny,keys });
					}
				}
			}
		}
	}
 
	cout << ans;
}

 

---

if (!OutofBound(nx, ny) && board[nx][ny] != '#' && !visited[nx][ny][keys])

방문 조건은 다음과 같다.

1. 범위를 벗어나지 않은 경우

2. 다음 좌표가 벽이 아닌 경우

3. 현재 열쇠 조합(keys)을 가지고 다음 좌표를 방문한 적이 없는 경우

 

// 빈 칸이거나 출발지거나 도착지
if (board[nx][ny] == '.' || board[nx][ny] == '0' || board[nx][ny] == '1') {
    visited[nx][ny][keys] = cnt + 1;
    q.push({ nx,ny,keys });
}

다음 좌표가 열쇠나 문이 아닌 경우 단순히 이동 횟수를 초기화한 후 큐에 삽입한다.

 

// 열쇠
else if (board[nx][ny] >= 'a' && board[nx][ny] <= 'f') {
    int key_number = board[nx][ny] - 'a';
 
    int newKeys = keys | (1 << key_number);
    if (!visited[nx][ny][newKeys]) {
        visited[nx][ny][newKeys] = cnt + 1;
        q.push({ nx,ny,newKeys });
    }
}

다음 좌표가 열쇠인 경우 비트마스킹을 통해 새로운 열쇠 조합을 계산한다. 만약 새로운 열쇠 조합을 가지고 다음 좌표에 방문한 적이 없다면 이동 횟수를 초기화하고 큐에 삽입한다.

 

// 문
else if (board[nx][ny] >= 'A' && board[nx][ny] <= 'F') {
    char door = board[nx][ny];
    char key = tolower(door);
    int key_number = key - 'a';
 
    // 열쇠를 가지고 있다면
    if (keys & (1 << key_number)) {
        visited[nx][ny][keys] = cnt + 1;
        q.push({ nx,ny,keys });
    }
}

다음 좌표가 문인 경우 문에 해당하는 열쇠(key)를 구한 후, 현재 열쇠 조합(keys)에 key가 존재하는지 확인한다. 만약 존재한다면 이동 횟수를 초기화한 후 큐에 삽입한다.

 

if (board[x][y] == '1') {
    ans = cnt - 1;
    break;
}

만약 현재 좌표가 목적지인 경우 답을 갱신하고 while문을 빠져나간다. BFS이기 때문에 가장 처음 만난 목적지까지 이동 횟수가 최소 이동 횟수이다.