[c++] BOJ 1194 :: 달이 차오른다 가자

난이도 : 골드 1

걸린 시간 : 많이

 

문제

달이 차오른다 가자 문제 바로가기

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

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

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

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

 

풀이

• bfs 사용
• (방문하는 위치, 가지고 있는 열쇠)가 메모이제이션 대상
• 가지고 있는 열쇠를 매번 있는 지 확인, 추가 연산해야하므로 순서가 있는 문자열이 아닌 순서가 고정되어 있는 bitmap 사용
  • A-F는 6개이므로 bitmap 사용이 문제가 되지 않는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <math.h>

using namespace std;

struct Node {
    int r, c;
    int path = 0;
    int keyBitmap;
    Node(int row, int col, int pathNum, int key) {
        r = row; c = col; path = pathNum;
        keyBitmap = key;
    }
};

int N, M;
char map[51][51];
vector<int> memo[51][51]; // A-F는 6개 => 6자리의 수로 표현
Node* start;
int direction[4][2] = { {0,1}, {-1, 0}, {1, 0}, {0, -1} };

int main() {
    // bfs

    int POWARR[6];
    for (int i = 0; i < 6; i++) // 미리 pow 저장
        POWARR[i] = pow(10, i);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++) {
            map[i][j] = str[j];
            if (map[i][j] == '0') { // char로 받을 때 주의!
                start = new Node(i, j, 0, 0);
            }
        }
    }

    fill(&memo[0][0], &memo[50][50], vector<int>()); // 키 저장

    int res = 1e8;

    queue<Node*> que;
    que.push(start);
    memo[start->r][start->c].push_back(start->keyBitmap);

    while (!que.empty()) {
        Node* pos = que.front(); que.pop();
        for (int i = 0; i < 4; i++) {
            int r = pos->r + direction[i][0];
            int c = pos->c + direction[i][1];
            int path = pos->path + 1;
            int key = pos->keyBitmap;
            if (r < 0 || c < 0 || r >= N || c >= M) // 맵 밖에 위치
                continue;
            if (map[r][c] == '1') { // 탈출
                cout << path;
                return 0;
            }
            if (memo[r][c].size()) { // 이미 같은 키를 가지고 들름
                if (find(memo[r][c].begin(), memo[r][c].end(), key) != memo[r][c].end())
                    continue;
            }
            if (map[r][c] == '#') // 벽
                continue;
            if (map[r][c] >= 'A' && map[r][c] <= 'F') {
                int index = map[r][c] - 'A';
                if((int)(key / POWARR[index]) % 10 == 0)
                    continue;
            }
            if (map[r][c] >= 'a' && map[r][c] <= 'f') {
                int index = map[r][c] - 32 - 'A';
                if ((int)(key / POWARR[index]) % 10 == 0)
                    key += POWARR[index];
            }
            que.push(new Node(r, c, path, key));
            if (find(memo[r][c].begin(), memo[r][c].end(), key) == memo[r][c].end())
                memo[r][c].push_back(key);
        }
    }
    cout << -1;
}

 

 

주의할 점

• 입력값을 string으로 받을 때 조건 처리를 char 형으로 해주어야 한다.

 

결과

아이디	메모리	시간	언어	코드 길이
gmldms784	3464	8	C++17 / 수정	2064