백준 3055번 탈출

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

기존의 BFS(Breadth First Search) 알고리즘을 적용하는 문제들과 달리 이 문제는 두더지가 이동하면서 물도 차오르기 때문에 큐를 두개 사용해야하는 문제였습니다.

두더지가 물이 차오를 예정인 위치까지도 움직일 수 없기 때문에 먼저 물이 차오르는 과정을 진행한 다음에 두더지를 움직이는 방식으로 진행했습니다.

river와 mole의 크기만큼 반복문을 돌리는 것이 핵심이였습니다!

#include <iostream>

#include <string>

#include <queue>

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 R, C;

pair<int, int> start, destination;

string graph[MAX];

queue<pair<int, int>> river;

int cache[MAX][MAX];

 

int BFS(void)

{

        queue<pair<int, int>> mole;

        mole.push(start);

        cache[start.first][start.second] = 1;

       

        while (!mole.empty())

        {

                 int curRiverSize = river.size();

                 //우선 물이 차오른다

                 for (int j = 0; j < curRiverSize; j++)

                 {

                         int curY = river.front().first;

                         int curX = river.front().second;

                         river.pop();

 

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

                         {

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

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

 

                                 if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C)

                                 {

                                          //빈칸으로

                                          if (graph[nextY][nextX]=='.')

                                          {

                                                  graph[nextY][nextX] = '*';

                                                  river.push(make_pair(nextY, nextX));

                                          }

                                 }

                         }

                 }

 

                 int curSize = mole.size();

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

                 {

                         int y = mole.front().first;

                         int x = mole.front().second;

                         mole.pop();

                        

                         //목적지 도달 시

                         if (y == destination.first && x == destination.second)

                                 return cache[y][x] - 1;

 

                         //두더지가 움직일 차례

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

                         {

                                 int nextY = y + moveDir[j].y;

                                 int nextX = x + moveDir[j].x;

 

                                 if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C)

                                          //돌과 물에 차 있는 곳으로 움직일 수 없다

                                          if (graph[nextY][nextX] != '*' && graph[nextY][nextX] != 'X' && cache[nextY][nextX] == 0)

                                          {

                                                  cache[nextY][nextX] = cache[y][x] + 1;

                                                  mole.push(make_pair(nextY, nextX));

                                          }

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        int result;

        cin >> R >> C;

 

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

        {

                 cin >> graph[i];

                 for (int j = 0; j < C; j++)

                         if (graph[i][j] == 'S')

                                 start = make_pair(i, j);

                         else if (graph[i][j] == '*')

                                 river.push(make_pair(i, j));

                         else if (graph[i][j] == 'D')

                                 destination = make_pair(i, j);

        }

 

        result = BFS();

 

        if (result == -1)

                 cout << "KAKTUS" << endl;

        else

                 cout << result << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

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