달이 차오른다, 가자.

문제 분석 및 풀이

설계, 분석

격자 그래프에서 최단경로를 찾는 문제.
최단경로는 BFS를 사용하는데, 여기서는 열쇠를 여부를 확인해야한다.

예전에 풀었던 벽 부수고 지나가기 처럼 BFS에 상태를 추가하는 풀이.

• visted 배열에 현재 획득한 키의 상태를 저장
  • 비트 마스크를 통해서 관리
• 현재 좌표를 현재 키 상태로 방문한 적 있으면 방문 불가
• 현재 좌표가 문
  • 열쇠가 없으면 방문 불가
• 현재 좌표가 열쇠
  • 열쇠 획득 처리

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

struct Pos
{
    int x;
    int y;
    int keyStatus = 0;
    int distance = 0;
};

int N, M;
string maze[50];
int visited[50][50][1<<7];
Pos startPos;


void GetKey(Pos& pos, int index)
{
    pos.keyStatus |= 1 << index;
}

bool KeyCheck(int keyStatus, int doorIndex)
{
    if ((keyStatus & 1 << doorIndex) == 0)
    {
        return false;
    }

    return true;
}

bool MoveToNextCell(Pos& next)
{
    // x,y 범위 넘으면 실패
    if (0 > next.x || next.x >= N) return false;
    if (0 > next.y || next.y >= M) return false;
    // 벽이면 실패
    if (maze[next.x][next.y] == '#') return false;

    // 이미 방문했으면 실패
    if (visited[next.x][next.y][next.keyStatus] == true) return false;

    // 열쇠
    if ('a' <= maze[next.x][next.y] && maze[next.x][next.y] <= 'f')
    {
        GetKey(next, maze[next.x][next.y] - 'a');
    }

    // 문
    if ('A' <= maze[next.x][next.y] && maze[next.x][next.y] <= 'F')
    {
        // 열쇠가 없는 경우
        if (KeyCheck(next.keyStatus, maze[next.x][next.y] - 'A') == false) return false;
    }
    
    return true;
}

void BFS(Pos start)
{
    queue<Pos> q;
    q.push(start);
    visited[start.x][start.y][start.keyStatus] = true;
    
    while(!q.empty())
    {
        auto f = q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            // RDLU 순으로 탐색
            int dx[] = {0,1,0,-1};
            int dy[] = {1,0,-1,0};

            Pos next = {f.x + dx[i], f.y + dy[i], f.keyStatus, f.distance + 1};
            if (MoveToNextCell(next))
            {
                visited[next.x][next.y][next.keyStatus] = true;
                if (maze[next.x][next.y] == '1')
                {
                    cout << next.distance << "\n";
                    return;
                }
                q.push(next);
            }
        }
    }
    cout << -1 << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // 입력
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string row;
        cin >> row;
        // 시작 지점
        auto zeroIndex = row.find("0");
        if (zeroIndex != string::npos)
        {
            startPos = {i, static_cast<int>(zeroIndex)};
        }
        maze[i] = row;
    }

    BFS(startPos);

    return 0;
}