[백준 2206번] 벽부수고 이동하기 (C++,BFS 변형)

아이디어

일단 문제를 보고 가중치도 없고, 최단거리를 찾길레 bfs를 사용했다.

그런데 벽을 부수고 안부수고의 상태를 저장하는 변수를 추가했고,

거리를 저장할 변수를 추가했다.

 

문제는 visited배열에서 생겼는데,

단순히 visited[x][y] 로는 풀리지 않고, visited[x][y][방문여부]를 추가해줘야한다.

이렇게 바꾸고나면

방문을 했느냐/안했느냐 이지선다가 아니라

 

아래와 같이 경우가 더 생긴다.

1. 벽을 부수지 않은 상태로 방문한경우 / 방문안한경우

2. 벽을 부순 상태로 방문한 경우 / 방문 안한경우

현재좌표 x,y에서 nx,ny(n : new) 로 이동하는데, 현재 x,y까지 오는데 벽을 부순적이 있는지 없는지에 따라 방문여부를 다르게 체크해주는 것이다. 왜냐하면 벽을 안부수고 nx,ny에 도달했을 때와 벽을 부수고 nx,ny에 도달했을 때 경로가 다를 것이기 때문이다.

 

내가 헤멘 부분이기 때문에 예시를 들어보자. visited[x][y]만 했을때의 반례로

 

(2,0)에 주목해보자.

이런경우 bfs특성상 파란색 경로가 먼저 도달해서 visited[2][0]을 true로 만들지만, 파란 경로를 따라가서는 목적지에 도달 할 수 없다.

그럼에도 불구하고 뒤늦게 도착한 초록 경로가 파란경로가 지나간 (2,0)을 지날 수 없게된다 (이미 visited[2][0]이 true이므로)

그래서 파란경로를 통해 진입한 2,0의 visited의 상태는

뒤에 벽을 안부수고 오는 경우를 생각하여 아래와 같이 두개의 visited상태를 가진다.

1. visited[2][0][1]( 1은 벽을 부수고 2,0에 진입) 

2. visited[2][0][0]( 0은 벽을 안부수고 2,0에 진입)

 

C++풀이

#include <bits/stdc++.h>
using namespace std;

int N,M;
int board[1001][1001];
bool visited[1001][1001][2];
queue<pair<pair<int,int>,pair<int,int>>> q; // x,y좌표 및 벽부순 여부 , count(거리)
int dx[4] = {-1, 0, 1, 0}; // 상 우 하 좌
int dy[4] = {0, 1, 0, -1};
int bfs(){
    visited[0][0][0] = true;
    visited[0][0][1] = true;
    q.push({{0,0},{0,1}}); //x,y와 벽 부순 횟수 0을 초기값으로 가짐.
    while(!q.empty())
    {
        int x=q.front().first.first;
        int y = q.front().first.second;
        int wall = q.front().second.first;
        int count = q.front().second.second;
        q.pop();
        if(x == N-1 && y == M-1) { // 목적지에 도착하면 
            return count;
        }
        for(int a = 0; a<4; a++)
        {
            int nx = x + dx[a];
            int ny = y + dy[a];
            //맵을 벗어나지 않았고, nx,ny에 방문한 적이 없을 때.
            if(nx >=0 && nx <=N-1 && ny >=0 && ny <= M-1 && visited[nx][ny][wall]==false)
            {
                if(wall ==0 && board[nx][ny] ==0) // 벽을 한번도 부순적이 없고, 벽없는 곳을 갈때.
                {
                    visited[nx][ny][wall] =true;
                    q.push({{nx,ny},{0,count+1}});
                }
                else if(wall ==0 && board[nx][ny] ==1) // 벽을 한번도 부순적이 없고, 벽있는 곳을 갈때.
                {
                    visited[nx][ny][wall] =true;
                    q.push({{nx,ny},{1,count+1}});
                }
                else if(wall ==1 && board[nx][ny] ==0) // 벽을 한번 부쉈고(더이상 못부숨) 벽없는 곳을 갈때.
                {
                    visited[nx][ny][wall] =true;
                    q.push({{nx,ny},{1,count+1}});
                }
                else if(wall==1 && board[nx][ny] ==1) //벽을 한번 부쉈고, 벽없는 곳을 갈때. (더이상 진행불가)
                {
                    //do nothing.
                }
            }
        }
    }
    //목적지에 도착 못하면
    return -1;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;

    //board setting
    for(int i = 0 ; i<N;i++)
    {
        string temp;
        cin >> temp;
        for(int j = 0 ; j<temp.size(); j++)
        {
            board[i][j] = temp[j]-'0';
        }
    }
    cout << bfs() ;


}

맨 위에게 내껀데 메모리가 생각보다 적다. 아무래도 queue에 집어넣을 때 구조체를 사용안하고 pair를 써서 그런것 같은데, 가독성이 떨어지는 문제가 있다. 다음부터는 struct를 사용해서 메모리는 조금 더 쓸지언정 가독성을 높이는 쪽이 좋아보인다.