백준 2206번 벽 부수고 이동하기

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

BFS(Breadth First Search) 알고리즘을 사용하여 푸는 문제였지만 벽을 한번 뚫을 수 있다는 조건이 있었기 때문에 살짝 까다로웠습니다.

벽을 뚫었는지 여부를 확인하기 위해 cache 배열을 삼중배열로 선언하였습니다.(마지막 2는 벽을 뚫는 기술을 사용했는지 여부)

따라서, 기존 문제들과는 다르게 갈 수 없는 벽이더라도 벽을 뚫는 기술이 있다면 큐에 넣으면서 최단거리를 확인하면 되는 문제였습니다.

주의할 점은, 이 문제에서는 시작점과 끝점을 포함한 경로라고 했으므로 cache[y][x][block] - 1이 아닌 cache[y][x][block]을 반환해줘야 AC 처리를 받을 수 있습니다!

#include <iostream>

#include <string>

#include <queue>

using namespace std;

 

const int MAX = 1000;

 

typedef struct

{

        int y, x;

}Dir;

 

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

 

int N, M;

int graph[MAX][MAX];

int cache[MAX][MAX][2]; //마지막 2는 벽 뚫기 여부

 

int BFS(void)

{

        queue < pair<pair<int, int>, int>> q; //y, x, 벽 뚫기

        q.push(make_pair(make_pair(0, 0), 1)); //시작점, 벽 뚫기 가능

        cache[0][0][1] = 1;

 

        while (!q.empty())

        {

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

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

                 int block = q.front().second;

                 q.pop();

 

                 //도착하면

                 if (y == N - 1 && x == M - 1)

                         return cache[y][x][block]; //시작하는 칸도 포함

 

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

                 {

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

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

 

                         if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M)

                         {

                                 //벽이 있고, 벽을 아직 안 뚫었다면

                                 if (graph[nextY][nextX] == 1 && block)

                                 {

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

                                          q.push(make_pair(make_pair(nextY, nextX), block - 1));

                                 }

                                 //벽이 없고 방문하지 않았던 곳이라면

                                 else if (graph[nextY][nextX] == 0 && cache[nextY][nextX][block] == 0)

                                 {

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

                                          q.push(make_pair(make_pair(nextY, nextX), block));

                                 }

                         }

                 }

        }

        return -1;

}

 

int main(void)

{

        cin >> N >> M;

 

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

        {

                 string temp;

                 cin >> temp;

 

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

                         graph[i][j] = temp[j] - '0';

        }

 

        cout << BFS() << endl;

        return 0;

}

개발환경:Visual Studio 2017

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