달이 차오른다, 가자

코드

[ 시간초과 코드 ]

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N,M,ans=1e9;
char board[55][55];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
map<char,bool> key;
pair<int,int> ms;
void DFS(int y, int x, int tot)
{
    queue<pair<int,int>> q;
    int cost[55][55];
    for(int i=0;i<N;i++)
        fill(cost[i], cost[i]+55, -1);
    cost[y][x] = 0;
    q.push({y,x});
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
            if(cost[ny][nx] >= 0 or board[ny][nx] == '#') continue;
            cost[ny][nx] = cost[cur.first][cur.second] + 1;
            /* 문을 만난다면 키가 있을때만 지나갈 수 있음 */
            if(board[ny][nx] >= 'A' and board[ny][nx] <= 'F'){
                if(!key[board[ny][nx]]) continue; // 키가 없으면 pass
            }else if(board[ny][nx] >= 'a' and board[ny][nx] <= 'f'){
                find++;
                if(key[board[ny][nx]-32]) goto jump; // 같은 문자가 이미 있으면 그냥 큐에 넣고 계속 하면 됨
                key[board[ny][nx] - 32] = true;
                char tmp = board[ny][nx];
                board[ny][nx] = '.';
                DFS(ny, nx, tot+cost[ny][nx]);
                // 백트래킹 - 복구
                board[ny][nx] = tmp;
                key[board[ny][nx] - 32] = false;
                continue;
            }else if(board[ny][nx] == '1'){
                ans = min(ans, tot+cost[ny][nx]);
                return;
            }
            jump:;
            q.push({ny,nx});
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == '0') ms = {i,j};
        }
    DFS(ms.first, ms.second, 0);
    if(ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}

• 풀이 & 한계
  • 열쇠('a' ~ 'f')를 만나면 해당 좌표부터 새로운 BFS를 수행 + map을 통해 현재 보유한 key관리
    (key는 백트래킹으로 나왔을 때에는 다시 false처리를 했음)
  • N과 M이 50이라는 큰 숫자에서 DFS를 했고, 최적 조건시 exit(0)할수도 없음
    --> 무조건 전부 수행해야 하니까 시간초과가 발생

• 필요한 로직
  : 3차원 배열 [key][ny][nx]를 통해서 board에 있을 때 현재 어떤 키를 보유한 상태인지에 따라 구분해서 관리하면 하나의 BFS로 수행 가능

---

[ 정답 풀이 - 비트마스킹 ]

#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N,M,ans=1e9;
char board[55][55];
bool vis[65][51][51]; // [key][ny][nx] --> 키가 총 6개니까 (1 << 6) 의 경우를 나눠줘야 한다
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
pair<int,int> ms;
// queue에 넣을 구조체
struct info{
    int y;
    int x;
    int cost;
    int key;
};
/* 현재 board에서 문 c를 만났을 때 내가 가진 key로 열 수 있는지 검사 */
bool checkKey(char c, int key){
    int result = key & (1 << ((int)c - 'A')); // 비트 마스킹
    if(result != 0) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == '0') ms = {i,j};
        }
    queue<info> q;
    info t = {ms.first, ms.second, 0, 0};
    q.push(t);
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.y + dy[dir];
            int nx = cur.x + dx[dir];
            int cur_cost = cur.cost;
            int key = cur.key;
            if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
            if(board[ny][nx] == '#' or vis[key][ny][nx]) continue;
            if(board[ny][nx] >= 'A' and board[ny][nx] <= 'F'){
                if(!checkKey(board[ny][nx], key)) continue; // 키가 없으면 Pass
            }else if(board[ny][nx] >= 'a' and board[ny][nx] <= 'f'){
                key = key | (1 << ((int)board[ny][nx]-'a')); // 비트 마스킹
            }else if(board[ny][nx] == '1'){ // BFS니까 발견하면 최단경로니 바로 종료
                cout << cur_cost + 1;
                return 0;
            }
            vis[key][ny][nx] = true;
            info t = {ny, nx, cur_cost+1, key};
            q.push(t);
        }
    }
    cout << -1;
    return 0;
}

• 로직
  • BFS를 수행하는데 queue에 4가지 정보를 유지 (y / x / cost / key)
  • 현재 어떤 키를 가지고 있는지 key 변수로 관리하며, 비트마스킹을 이용해서 경우를 나눔
    --> 비트마스킹 + shift연산 으로 현재 가진 키를 표현
    --> ex)
    키 a를 가짐 : 000001
키 a,d를 가짐 : 001001
    ... key는 총 6개니까 (1<<6) 즉, 키를 가지는 경우는 총 64개가 나온다
  • BFS를 수행하면서 board값이 1인 점을 만나면 바로 종료
    --> BFS니까 최단 경로를 의미

• 느낀 점
  • 프로그래머스의 활주로 건설 처럼 최단경로를 구하는데,
    각 board에서 다양한 상태를 가질 수 있다면 3차원 배열을 이용해서 하나의 BFS로 풀어낼 수 있음
  • 비트마스킹 + shift 연산으로 key값을 관리하는 것이 매우 신기