달이 차오른다, 가자. (feat. 백준, 1194번)

달이 차오른다, 가자.
https://www.acmicpc.net/problem/1194

1194번: 달이 차오른다, 가자.

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int N, M, dx[4], dy[4];
char arr[51][51];
bool visit[51][51][1 << 6];
int bfs(register int x, register int y){
    memset(visit, false, sizeof(visit));
    register int cnt, key;
    queue<tuple<int, int, int, int>> q;
    q.push(make_tuple(x, y, 0, 0));
    visit[x][y][0] = true;
    while(!q.empty()){
        auto p = q.front(); q.pop();
        x = get<0>(p), y = get<1>(p), cnt = get<2>(p), key = get<3>(p);
        if(arr[x][y] == '1'){
            return cnt;
        }
        for(register int d = 0, nx, ny; d < 4; ++d){
            nx = x + dx[d], ny = y + dy[d];
            if(1 <= nx && nx <= N && 1 <= ny && ny <= M && !visit[nx][ny][key] && arr[nx][ny] != '#'){
                if('a' <= arr[nx][ny] && arr[nx][ny] <= 'f'){
                    auto nkey = key | (1 << (arr[nx][ny] - 'a'));
                    if(!visit[nx][ny][nkey])
                        visit[nx][ny][nkey] = true, q.push(make_tuple(nx, ny, cnt + 1, nkey));
                }
                else if('A' <= arr[nx][ny] && arr[nx][ny] <= 'F'){
                    if(key & (1 << (arr[nx][ny] - 'A')))
                        visit[nx][ny][key] = true, q.push(make_tuple(nx, ny, cnt + 1, key));
                }
                else
                    visit[nx][ny][key] = true, q.push(make_tuple(nx, ny, cnt + 1, key));
            }
        }
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> N >> M;
    register int x, y;
    for(register int n = 1, m; n <= N; ++n)
        for(m = 1; m <= M; ++m){
            cin >> arr[n][m];
            if(arr[n][m] == '0')
                x = n, y = m;
        }
    cout << bfs(x, y);
    return 0;
}
// *&)*@*

 

반응형

1. 한시간이 꼬박 걸렸습니다.
2. 핵심은 보통 bfs에서 사용하는 전체 맵에 마킹을 해주는게 아니라 개별 맵에 마킹을 해주어야 합니다.
3. 즉 내가 수행한 루트의 좌표뿐만 아니라 결과까지 queue에 삽입하여 다음번에 참조해야 합니다.
4. 따라서 좌표뿐만 아니라 이동 횟수와 보유한 키의 종류까지 함께 들고 있어야 합니다.