문제를 해결하는 과정

문제의 조건들 중에서 하나는 벽을 최대 1개까지 부수고 이동할 수 있는 것이다.
따라서 이동 중에 벽을 부수게 되면 그 다음 동작부터는 벽을 이미 부순 경험이 있다는 표식을 남겨야 한다.

이동할 수 있는 경우는 크게 두 가지

• 벽이 존재( '1' )하지만 아직 벽을 없앤 경험이 없을 경우
• 벽이 없는( '0' ) 경우

그러면 이제 반복을 통해 현재 위치에서 이동할 수 있는 곳의 거리값을 업데이트를 해준다.
거리값을 업데이트 해주었다면 큐에 push하고 이 과정을 반복한다.

그런데 BFS로 시도할 경우 한 가지 문제가 발생한다.

• 주황색 경로는 벽을 부수고 더 빠르게 이동하는 경우
• 파란색 경로는 벽을 부수지 않고 우회해서 이동하는 경우

그림과 같이 경로가 겹치게 되는 구간이 생긴다.

거리값은 주황색 경로가 훨씬 빠르지만 도착을 하지 못했다.
반면에 파란색 경로는 거리값이 더 컸지만 도착을 했다.

결국 거리값이 더 작은 경로가 무조건 정답이 될 수는 없다는 것

이에 대한 해결책으로 두 가지 경우를 모두 확인하면서 진행하는 방법이 있다.

좌표가 (x,y) 인 특정 구간까지의 거리값을 2개로 나눠 저장한다.

1. 벽을 부수지 않은 채로 (x,y)까지 이동했을 때 거리값
2. 벽을 부수고 이동해서 (x,y)까지 이동했을 때 거리값

거리값을 나타내는 변수를 dist라고 하면 배열의 선언은

dist[height][width][2]

dist[y][x][0] // 1번 경우의 거리값을 저장
dist[y][x][1] // 2번 경우의 거리값을 저장

이런 방법으로 거리값을 구하면 위의 경우를 문제없이 통과할 수 있다.

코드 작성

큐에 값을 넣을 때에는 좌표값 (x,y) 와 벽을 부순 경험(표식)이 있는지 확인하는 값까지 총 3개를 준비한다.

벽을 부순 적이 있다면 값은 '1'
벽을 아직 부수지 않았다면 값은 '0'

q.push(q.push(make_pair( make_pair(좌표 변수 2개),표식 유무 변수 1개));)

전체 코드는 다음과 같다.

#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;

int ShortestPath(); // 최단경로를 찾는 함수 선언
bool input_data[1001][1001]; // 입력값을 받는 배열, 벽이 있으면(1) True, 벽이 없으면(0) False
int dist[1001][1001][2]; // 거리값을 저장할 배열
int height;
int width;

// 현재위치에서 동,남,서,북 방향을 가르키는 좌표
int direction_row[4]={0,1,0,-1};
int direction_col[4]={1,0,-1,0};

int main(){
    cin >> height >> width;
    for (int i = 1; i < height+1; i++)
    {
        string str;
        cin >> str;
        for (int j = 1; j < width+1; j++)
        {
            input_data[i][j]=str[j-1] - '0';
        }
    }
    cout << ShortestPath();
}

int ShortestPath()
{
    queue< pair< pair<int, int> , int > > q;
    q.push(make_pair( make_pair(1,1), 0 ));
    dist[1][1][0]=1;

    while(!q.empty()){
        int curr_level_node=q.size();
        while(curr_level_node!=0){
            // 현재 위치의 좌표, 벽이 부셔진 상태인지 아닌지, 현재 위치까지의 거리값을 불러낸다.
            int row=q.front().first.first;
            int col=q.front().first.second;
            int curr_wall=q.front().second;
            int curr_value=dist[row][col][curr_wall];
            q.pop();
            // 최단 경로를 찾는데 성공하면 값을 리턴
            if(row==height && col==width){
                return dist[row][col][curr_wall];
            }

            curr_level_node--;
            // 동,서,남,북의 4방향을 체크하여 이동이 가능하면 거리값 업데이트, 이동한 방향의 좌표를 큐에 push
            for (int i = 0; i < 4; i++)
            {
                int moved_row=row+direction_row[i];
                int moved_col=col+direction_col[i];
                
                if( (0 < moved_row && moved_row <= height) && (0 < moved_col && moved_col <= width) ){
                    // 벽이 없고('0'인 경우) 아직 방문을 안했을 경우 
                    if(input_data[moved_row][moved_col]==0 && dist[moved_row][moved_col][curr_wall]==0){
                        dist[moved_row][moved_col][curr_wall]=curr_value+1;
                        q.push(make_pair( make_pair(moved_row,moved_col),curr_wall));
                    }
                    // 벽이 있지만('1'인 경우) 아직 벽을 깬 적이 없을 경우(벽을 깰 수 있는 상태인 경우) 
                    if(input_data[moved_row][moved_col]==1 && curr_wall==0){
                        dist[moved_row][moved_col][curr_wall+1]=curr_value+1;
                        q.push(make_pair(make_pair(moved_row,moved_col),curr_wall+1));
                    }                    
                }
            }
        }
    }
    return -1;
}