[백준] 1194번 달이 차오른다, 가자
1194 달이 차오른다 가자
문제
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다
빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨
벽 : 절대 이동할 수 없다. (‘#’
열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
풀이)
bfs와 bit-masking을 이용해서 푼 문제이다. 복잡하다.
key를 하나만 가질 수 있는게 아니고 여러 개를 동시에 가질 수 있다.
key를 가진 상태를 키가 6개니깐 6 비트로 표현했다.
0번째 비트는 a, 1번째 비트는 b, 2번째 비트는 c 이런식으로.
f e d c b a
5 4 3 2 1 0
비트 상태 integer
0 0 0 0 0 0 -> 0, 아무 키도 가지고 있지 않은 상태
0 0 0 0 0 1 -> 1, a키만 가지고 있는 상태
0 0 0 0 1 0 -> 2, b키만 가지고 있는 상태
0 0 0 0 1 1 -> 3, a키와 b키를 가지고 있는 상태
.
.
0 1 0 0 0 0 -> 16, e키만 가지고 있는 상태
.
.
1 0 0 1 0 1 -> 35, a키와 c키 f키를 가지고 있는 상태
.
.
1 1 1 1 1 1 -> 63, 모든 키를 가지고 있는 상태
그리고 키를 가진 상태에 따라 맵을 이동하는데 중복된 곳은 피하기 위해
bool visited[50][50][64] 3차원 배열로 방문한 곳을 표시하기로 했다.
bool visited[i][j][k] == true 는 i 행 j 열 번째 칸을 key상태가 k일 때 방문했었다 라는 뜻이다.
주의
키를 나타내는 a, b, c, d, e, f는 ASCII로 97~102이다.
문을 나타내는 A, B, C, D, E, F는 ASCII로 65~102이다.
코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include <stdio.h> #include <vector> #include <queue> #include <algorithm> using namespace std; int n, m; char map[50][50]; int dy[4] = { -1,1,0,0 }; int dx[4] = { 0,0,-1,1 }; pair<int, int> minsik; //key를 000000 6비트로 표시, 비트가 1일경우 해당하는 열쇠를 가진다는뜻 //0 0 0 0 0 0 //f e d c b a bool visited[50][50][64]; int bfs() { queue<pair<pair<int, int>,int>>qu;//좌표와 열쇠종류 qu.push({ { minsik.first, minsik.second } ,0}); visited[minsik.first][minsik.second][0] = true; //일단 아무 열쇠를 가지지 않은 경우 int cnt = 0; while (!qu.empty()) { int size = qu.size(); while (size--) { int y = qu.front().first.first; int x = qu.front().first.second; int key = qu.front().second; qu.pop(); for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny >= 0 && ny < n && nx >= 0 && nx < m) { //이미 접근했었거나 벽이면 pass if (visited[ny][nx][key] || map[ny][nx] == '#')continue; if (map[ny][nx] == '1') return cnt + 1;//만일 미로 탈출할 수 있다면 if (map[ny][nx] == '.' || map[ny][nx] == '0') {//빈곳일 경우 visited[ny][nx][key] = true; qu.push({ {ny,nx} ,key }); } else {//열쇠거나 문일경우 int temp = (int)map[ny][nx]; //a~f = 97~102, A~F = 65~70 if (temp > 90) {//열쇠 temp -= 97; if (key & (1 << temp)) { //temp번째 열쇠를 이미 가지고 있었다면 visited[ny][nx][key] = true; qu.push({ {ny,nx} ,key }); } else { //열쇠 추가 visited[ny][nx][key | (1 << temp)] = true; //temp번째 비트도 1로 바꾼다. qu.push({ {ny,nx} ,key | (1 << temp) }); } } else {//문 temp -= 65; if (key & (1 << temp)) {//temp번째 문에 해당하는 열쇠를 가지고 있었다면 visited[ny][nx][key] = true; qu.push({ {ny,nx} ,key }); } //안가지고 있다면 이동 불가 } } } } } cnt++; } return -1; } int main() { scanf("%d %d", &n, &m); getchar(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%c", &map[i][j]); if (map[i][j] == '0') minsik = { i,j }; } getchar(); } printf("%d", bfs()); return 0; } | cs |
결과)
