[Algorithm/C++17] 백준 2206 벽 부수고 이동하기

문제

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

풀이 방법

(1,1)에서 (N,M)까지의 거리를 구하는 문제이다. 시작점과 도착점까지의 거리를 구하는 미로탐색과 비슷한 문제로, BFS로 해결할 수 있다. 다만 이 문제는 미로의 벽 하나를 부술 수 있다는게 차이점이다.

그렇다면 기존의 BFS 알고리즘에 벽을 부쉈는지, 안부쉈는지에 대해 추가로 처리해줘야 한다. 따라서 탐색 노드를 좌표뿐만 아니라 벽을 부쉈는지 안부쉈는지에 대한 flag까지 같이 넣어준다.

큐의 형태는 queue<tuple<int, int, int>>가 되고 각각의 의미는 y좌표, x좌표, 벽을 부쉈는지 여부이다.

또한 방문 여부도 bool visited[y][x][flag]로 저장하게 된다.

다시 말해 2차원 공간이었던 미로를 3차원으로 확장해서 벽을 부순 미로, 부수지 않은 미로가 있다고 보면 된다.

 

탐색은 다음과 같이 진행한다.

인접 노드에 벽이 없다면 그대로 탐색을 진행하면 된다.

인접 노드에 벽이 있다면 벽을 부수지 않은 경우에 한해서 부숴서 탐색을 진행해본다. 이때 부쉈으면 노드를

(ny, nx, 1)로 넣어 flag를 1로 바꿔 벽을 부순 공간을 탐색하게 만든다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int dy[] = {-1,0,0,1};
int dx[] = {0,-1,1,0};
int main() 
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> matrix(n+1, vector<int>(m+1, 0));
    int visited[1001][1001][2] = {0,};
    for(int i=1; i<=n; i++) 
    {
        for(int j=1; j<=m; j++) 
        {       
            scanf("%1d", &matrix[i][j]);
        }
    }
    bool success = false;
    queue<tuple<int,int,int>> q;
    q.push({1,1,0});
    visited[1][1][0] = 1;
    while(!q.empty())
    {
    	auto t = q.front();
    	int y = get<0>(t);
    	int x = get<1>(t);
    	int crash = get<2>(t);
        q.pop();
        if(y==n && x==m)
        {
            success = true;
            break;
        }
        for(int i=0; i<4; i++)
        {
            int ny = y+dy[i];
            int nx = x+dx[i];
            if(1<=ny && ny<=n && 1<=nx && nx<=m)
            {
            	if(visited[ny][nx][crash] !=0) continue;
            	if(matrix[ny][nx] == 0)
            	{
            		visited[ny][nx][crash] = visited[y][x][crash]+1;
            		q.push({ny,nx,crash});
            	}
            	else
            	{
            		if(crash == 1) continue;
            		visited[ny][nx][1] = visited[y][x][0]+1;
            		q.push({ny,nx,1});
            		
            	}
            }
        }
    }
    if(success)
    {
        if(visited[n][m][0]) printf("%d", visited[n][m][0]);
        else if(visited[n][m][1]) printf("%d", visited[n][m][1]);
    }
    else
        printf("-1");
    return 0;
}

고찰

처음에 벽을 부쉈다는 상태를 어떻게 알고리즘으로 구현할까 생각하다가 백트래킹을 활용해야 하는 줄 알았으나 애초에 상태 자체를 그래프의 노드로 만들어 탐색하면 되는 문제였다.

질문게시판에 djm03178님이 남겨주신 좋은 글이 있어 링크를 남긴다.

https://www.acmicpc.net/board/view/27386

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★