[BOJ] 벽 부수고 이동하기_2206 C++ 풀이

문제

N X M으로 표현된 맵이 있다. 0은 이동할 수 있는 곳을 나타내고 1은 이동할 수 없는 벽을 나타낸다. $($1,1)에서 $($N,M)으로 최단 경로로 이동하려 한다. 한칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이며 한번 벽을 깨고 이동할 수 있다. 경로에는 시작하는 칸과 도착하는 칸을 포함할때 최단 경로를 출력하는 프로그램을 작성하라.

접근 방법

1600번 말이 되고픈 원숭이와 비슷한 문제였다. 일단 N개의 줄에 M개의 숫자로 주어지는 맵의 예제 입력이 다음과 같이 수들 사이에 빈칸이 없기 때문에 ->
6 4
0100
1110
1000
0000
0111
0000

cin>>map[i][j]; 로 입력 받는 다면 0, 1 따로 입력 받는게 아니라 0100을 하나의 수로 취급하여 입력 받게 된다. 때문에 0100을 문자열로 취급하여 입력 받은 다음 각 문자열의 인덱스 값에서 ‘0’을 빼서 map 이차원 배열에 정수값을 입력해 주었다.

최단 경로를 구하기 위해 BFS를 사용하였고 큐에 $($row, col, 경로수, 벽 부순 횟수)등을 pair로 저장하여 관리하였다. 방문한 정점이 벽을 뚫고 온건지 아닌지 구별 하기 위해서 visited 배열을 3차원 배열로 선언해 주었다. visited[row][col][ability]

상하좌우는 구조체를 사용하여 x값, y값을 더하여 상하좌우 이동을 나타내었다.

구현

#include<iostream>
#include<queue>
#include<string>
#define MAX 1000
using namespace std;

typedef struct
{
    int x,y;
} D;

D dir[4] = { {0,1}, {0,-1}, {1,0}, {-1,0} };// 상하좌우 이동

int map[MAX][MAX];
int visited[MAX][MAX][2];
int n, m;

int bfs(void)
{
    queue<pair<pair<int, int>, pair<int, int> > > q;
    q.push(make_pair(make_pair(0,0),make_pair(1,0)));
    visited[0][0][0]=1;
    
    while(!q.empty())
    {
        int row = q.front().first.first;
        int col = q.front().first.second;
        int cnt = q.front().second.first;
        int ability = q.front().second.second;
        q.pop();

        if(row == n-1 && col == m-1) return cnt;

        if(ability==0)
        {
            for(int i=0; i<4; i++)
            {
                int nextRow = row + dir[i].x;
                int nextCol = col + dir[i].y;
                if(0<=nextRow && nextRow<n && 0<=nextCol && nextCol<m)
                    if(map[nextRow][nextCol]==1 && !visited[nextRow][nextCol][1])
                    {
                        q.push(make_pair(make_pair(nextRow, nextCol), make_pair(cnt+1, ability+1)));
                        visited[nextRow][nextCol][ability+1]=1;
                    }
            }
        }

        for(int i=0; i<4; i++)
        {
            int nextRow = row + dir[i].x;
            int nextCol = col + dir[i].y;
            if(0<=nextRow && nextRow<n && 0<=nextCol && nextCol<m)
                if(map[nextRow][nextCol]==0 && !visited[nextRow][nextCol][ability])
                {
                    q.push(make_pair(make_pair(nextRow, nextCol), make_pair(cnt+1, ability)));
                    visited[nextRow][nextCol][ability]=1;
                }
        }
    }
    return -1;
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string str[MAX];

    cin>>n>>m;

    for(int i=0; i<n; i++) cin>>str[i];

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            map[i][j]=str[i][j]-'0';

    cout<<bfs();
    return 0;
}

BOJ_벽 부수고 이동하기