달이 차오른다, 가자.
문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. ('.')
- 벽: 절대 이동할 수 없다. ('#')
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
예제 입력
1 7
f0.F..1
예제 출력
7
풀이
이전까지의 탐색 문제들과 비슷하다 생각했는데 열쇠를 획득했을때 방문했던곳도 다시 돌아갈 수 있는걸 고려해야 했다.
획득한 열쇠의 종류에 따라 탐색을 계속 진행해준다.
#include <iostream>
#include <vector>
#include <time.h>
#include <queue>
using namespace std;
//abcdef
#define A 0b00000001
#define B 0b00000010
#define C 0b00000100
#define D 0b00001000
#define E 0b00010000
#define F 0b00100000
char **board;
int width, height, answer;
int key[6] = {A, B, C, D, E, F};
queue<pair<int, int>> xyQueue;
queue<pair<int, int>> infoQueue;
bool outOfrange(int x, int y)
{
if(y == height || y == -1 || x == width || x == -1)return true;
else return false;
}
int Xdirection[4] = {0, 0, -1, 1};
int Ydirection[4] = {-1, 1, 0, 0};
bool visited[50][50][64];
int searchBFS(){
while(xyQueue.empty() == 0 || infoQueue.empty() == 0)
{
int x = xyQueue.front().first;
int y = xyQueue.front().second;
int keyList = infoQueue.front().first;
int cnt = infoQueue.front().second;
if(board[y][x] == '1')return cnt;
for(int i = 0; i < 4; i++)
{
int nx = x + Xdirection[i];
int ny = y + Ydirection[i];
int tempKeyList = keyList;
//방문 or 막다른길
if(outOfrange(nx, ny))continue;
if(board[ny][nx] == '#' || visited[ny][nx][keyList])continue;
visited[ny][nx][keyList] = true;
//문인 경우
if(board[ny][nx] >= 'A' && board[ny][nx] <= 'F'){
//열쇄가 없으면
if((key[board[ny][nx]-'A'] & keyList) == 0)continue;;
}
//키를 처음 줍는경우
else if(board[ny][nx] >= 'a' && board[ny][nx] <= 'f'){
if((key[board[ny][nx]-'a'] & keyList) == 0){
tempKeyList += key[board[ny][nx]-'a'];
}
}
xyQueue.push(make_pair(nx, ny));
infoQueue.push(make_pair(tempKeyList, cnt + 1));
}
xyQueue.pop();
infoQueue.pop();
}
return -1;
}
int main(){
int startX, startY;
cin >> height >> width;
answer = 0x7fffffff;
board = new char* [height];
for(int y = 0; y < height; y++){
board[y] = new char[width];
for(int x = 0; x < width; x++){
cin >> board[y][x];
if(board[y][x] == '0')startX = x, startY = y;
}
}
xyQueue.push(make_pair(startX, startY));
infoQueue.push(make_pair(0, 0));
answer = searchBFS();
cout << answer;
}
'알고리듬 > 문제' 카테고리의 다른 글
[baekjoon] 7569 (0) | 2023.04.17 |
---|---|
[baekjoon] 7453 (0) | 2023.04.15 |
[baekjoon] 12100 (0) | 2023.03.23 |
[baekjoon] 14502 (0) | 2023.03.21 |
[baekjoon] 16234 (0) | 2023.03.20 |