[백준 2206] 벽 부수고 이동하기

벽 부수고 이동하기

문제 설명

N,M의 값을 입력받고 0일때는 이동이 가능하다. 1인경우 벽이기 때문에 이동할 수 없다.
하지만 단 한번 벽을 부수고 이동하는 것이 가능하다. 최적 이동경로를 구하도록 하자.

---

알고리즘

1. 입력 값을 모두 입력 받은 뒤 (0,0)에서 시작하고 벽을 뚫을 수 있는 지 여부를 나타내기위해 visited에 배열을 한 차원 추가한다.
2. BFS 알고리즘을 사용하여 현재 그래프가 0이고 방문하지 않은 경우는 접근이 가능하다.
3. 그래프가 1이고 현재 block이라는 변수가 1일때는 벽을 부수고 방문하는 것이 가능하다.
   이때 값을 계산할 때 한 번 부쉈기 때문에 1을 0으로 바꾸어 준다.
4. 이동 할 수 없는 경우 -1을 반환한다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;
#define MAX 1000

int graph[MAX][MAX];
int visited[MAX][MAX][2];
int answer = 0;
int N, M;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };

int bfs(int x, int y)
{
    queue < pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(x,y),1));//첫 값 불러오기
    visited[x][y][1] = 1;
    while (!q.empty())
    {
        x = q.front().first.first;//queue의 앞의 값 불러오기 
        y = q.front().first.second;
        int block = q.front().second;
        q.pop();

        if (x == N - 1 && y == M - 1)
            return visited[N-1][M-1][block]; //시작하는 칸도 포함

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];//위치이동 반경 계산
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)//범위내에 해당하는 부분이면 
            {
                if (graph[nx][ny] == 0 && visited[nx][ny][block] == 0)//주변에 벽이 없고 방문하지 않아서 방문 해도 되는 경우 
                {
                    visited[nx][ny][block] = visited[x][y][block] + 1;
                    q.push(make_pair(make_pair(nx,ny),block));
                }
                else if (graph[nx][ny] == 1 && block == 1)//주변에 벽이 있고 아직 안뚫은 경우 
                {
                    visited[nx][ny][block-1] = visited[x][y][block] + 1;
                    q.push(make_pair(make_pair(nx, ny), block-1));
                }
            }
        }        
    }
    return -1;
}

int main(void)
{
    cin >> N>>M;
    for (int i = 0; i < N; i++)//연결 관계 입력 받기
    {
        string x;
        cin >> x;
        for (int j = 0; j < M; j++)
            graph[i][j] = x[j] - '0';
    }

    cout << bfs(0, 0) << endl;

    return 0;
}

---

고찰

길 찾기 문제와 동일한 구조이지만 벽을 한 번 부술 수 있어서 난이도가 매우 높아졌다.
처음에는 bool 타입으로 flag를 주어서 만들려고 했지만 그런식으로 풀면 갈 수 없는 -1을 반환하는 경우를 판단 할 수 없게 되어서 방법이 떠오르지 않아서 검색을 해서 겨우 풀 수 있었다.

방문 여부를 판단하는 visited[MAX][MAX][2]를 보면 3차원 배열인데, 마지막은 2칸이다. 인덱스 1번째 부분에 값이 저장 되어있고 그 뒤에는 전부 0으로 만들어 준다.