[BOJ] 달이 차오른다, 가자

문제

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

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

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

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

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

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

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

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

 

입력

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

 

 

풀이

1194

맞았습니다!!

2284

4

C++14 / 수정

2422

1분 전

 

1. BFS 탐색 문제

 

2. 생각 해야 할 점은 탐색을 할 때마다 갖고 있는 열쇠들을 함께 저장 해야한다. 

 

3. 0이 현재 민수가 있는 위치이기 때문에 큐에 제일 먼저 넣어주고 이 좌표를 기준으로 탐색을 시작. (키의 초기값은 0) -> 시작할 때는 아무런 키도 갖고 있지 않기 때문에 

 

4. 현재 좌표가 1이라면 출구를 찾았기 때문에 큐 탐색에서 탈출합니다. (최소값 비교가 필요하다)

 

5. 초기에는 아무 키도 갖고 있지 않기 때문에 0으로 입력합니다. (6bits로 선언)

 

• 그리고 키를 만난다면 [ 1 << 키의 값 - 'a' ] 와 현재의 키 값을 OR(|) 연산을 하여 키 값을 저장
• 문을 만났다면 현재 가지고 있는 키 값과 문의 값( A ~ F) 를 AND 연산을 통해 동일한지 판단하여 같지 않다면 (==0) 다른 방향으로 탐색한다. 

 

6. 방문 여부를 표시하는 삼차원 배열 visited 에 현재의 좌표와 키의 값에 방문을 표시하고 큐에 푸시.

---

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m, ans = 987654321;
char map[51][51]; //맵을 저장 
 
bool visited[51][51][1<<6]; //키를 가지고 현재 방문한 좌표를 표시 
 
typedef pair<int, int> pp;
typedef pair<pp, int> ppp;
pp pos;
 
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
 
//각 열쇠를 가지고 간것과 아닌 것을 판별하는 visited  
 
void bfs()
{
    queue<ppp> q;
 
    q.push(ppp(pos, 0)); 
    visited[pos.first][pos.second][0] = true;
 
    int step = 0;
 
    while (!q.empty())
    {
        int size = q.size();
 
        while (size--)
        {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int key = q.front().second;
            
 
            q.pop();
 
            if (map[x][y] == '1')
            {
                ans = min(ans, step);
                break;
            }   
 
            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int nKey = key;
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny][nKey] || map[nx][ny] == '#')
                    continue;
 
                if ('A' <= map[nx][ny] && map[nx][ny] <= 'F')
                {
                    //열쇠가 있으면 들어갈 수 있다.
                    int tmp = (1<< map[nx][ny] -'A'); 
                    //문의 종류를 찾는다. 
                    if (!(key & tmp)) 
                        continue;
                    
                }
                else if ('a' <= map[nx][ny] && map[nx][ny] <= 'f') {
                    
                    int tmp = (1<<map[nx][ny] - 'a');
                    nKey = (key | tmp);
                }
 
                visited[nx][ny][nKey] = true;
                q.push(ppp(pp(nx, ny), nKey));
            }
        } //while size
        step++;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
 
            if (map[i][j] == '0')
            {
                //민식의 위치
                pos = pp(i, j);
            }
        }
    }
    //input
    bfs();
 
    if (ans == 987654321) cout << -1 << '\n';
    else cout << ans << '\n';
 
    return 0;
}