백준 1194번 달이 차오른다, 가자

문제 링크입니다: https://www.acmicpc.net/problem/1194

백준 9328번 열쇠(http://jaimemin.tistory.com/692)처럼 열쇠가 주어진 BFS(Breadth First Search) 알고리즘 문제였습니다.

하지만 9328번과 다르게 해당 문제에는 열쇠가 6개 밖에 없고 한 열쇠를 한 번 이상 사용할 수 있기 때문에 비트를 이용해 열쇠를 표현하는 것이 바람직합니다.

알고리즘은 아래와 같습니다.

1. 미로를 입력받고 출발점을 찾습니다.

2. 출발점으로부터 전형적인 BFS 탐색을 시작합니다.

i) 열쇠를 얻는 순간 다시 모든 곳을 탐색할 수 있어야하므로 visited를 key, y, x에 대해 삼차원 배열로 선언합니다.

ii) 열쇠를 주우면 OR 연산을 통해 소지한 열쇠를 업데이트하고 소지한 열쇠가 바뀌었다면 큐에 넣습니다.

iii) 잠긴 문에 도달하면 AND 연산을 통해 가진 열쇠를 통해 문을 열 수 있는지 파악하고 이동이 가능한지 파악합니다.

3. 도착점에 도달하면 여태까지 움직인 거리를 반환합니다.

4. 도착점에 도달하지 못하면 -1을 반환합니다.

#include <iostream>

#include <string>

#include <queue>

#include <cstring>

using namespace std;

 

const int MAX = 50;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N, M;

string maze[MAX];

bool visited[64][MAX][MAX]; //key, y, x

 

int BFS(int y, int x)

{

        queue<pair<pair<int, int>, pair<int, int>>> q; //y, x, cnt, key(bit로 표현)

        q.push({ {y, x}, {0, 0} });

        visited[0][y][x] = true;

 

        while (!q.empty())

        {

                 int curY = q.front().first.first;

                 int curX = q.front().first.second;

                 int cnt = q.front().second.first;

                 int key = q.front().second.second;

                 q.pop();

 

                 if (maze[curY][curX] == '1')

                         return cnt;

 

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = curY + moveDir[i].y;

                         int nextX = curX + moveDir[i].x;

 

                         if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M && !visited[key][nextY][nextX] && maze[nextY][nextX] != '#')

                         {

                                 if (maze[nextY][nextX] == '.' || maze[nextY][nextX] == '0' || maze[nextY][nextX] == '1')

                                 {

                                          visited[key][nextY][nextX] = true;

                                          q.push({ {nextY, nextX}, {cnt + 1, key} });

                                 }

                                 else if ('a' <= maze[nextY][nextX] && maze[nextY][nextX] <= 'f')

                                 {

                                          int newKey = key | (1 << (int(maze[nextY][nextX]) - 97));

                                          if (!visited[newKey][nextY][nextX])

                                          {

                                                  visited[key][nextY][nextX] = true;

                                                  visited[newKey][nextY][nextX] = true;

                                                  q.push({ {nextY, nextX}, {cnt + 1, newKey} });

                                          }

                                 }

                                 else if ('A' <= maze[nextY][nextX] && maze[nextY][nextX] <= 'F')

                                 {

                                          if (key & 1 << (int(maze[nextY][nextX]) - 65))

                                          {

                                                  visited[key][nextY][nextX] = true;

                                                  q.push({ { nextY, nextX },{ cnt + 1, key } });

                                          }

                                 }

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        pair<int, int> start;

 

        for (int i = 0; i < N; i++)

        {

                 cin >> maze[i];

                 for (int j = 0; j < maze[i].length(); j++)

                         if (maze[i][j] == '0')

                         {

                                 start.first = i;

                                 start.second = j;

                         }

        }

 

        cout << BFS(start.first, start.second) << "\n";

 

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~