백준 2206 벽 부수고 이동하기 - C++, BFS

2206번: 벽 부수고 이동하기

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

int n, m;
int goX[4] = { 0, 0, 1, -1 };
int goY[4] = { 1, -1, 0, 0 };
int map[1001][1001];
int arr[1001][1001][2];

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

    while(!q.empty()){
        int curX = q.front().first.first;
        int curY = q.front().first.second;
        int count = q.front().second;
        q.pop();

        if(curX == m-1 && curY == n-1)
            return arr[curY][curX][count];
        
        for(int i = 0; i < 4; i++){
            int nextX = curX + goX[i];
            int nextY = curY + goY[i];

            if(nextX >= 0 && nextX <= m-1 && nextY >= 0 && nextY <= n-1){
                if(map[nextY][nextX] == 1 && count){
                    arr[nextY][nextX][0] = arr[curY][curX][count] + 1;
                    q.push(make_pair(make_pair(nextX, nextY), 0));
                }
                else if(map[nextY][nextX] == 0 && arr[nextY][nextX][count] == 0){
                    arr[nextY][nextX][count] = arr[curY][curX][count] + 1;
                    q.push(make_pair(make_pair(nextX, nextY), count));
                }
            }
        }
    }
    return -1;
}

int main(){
    scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++){
        string line;
        cin >> line;
        for(int j = 0; j < m; j++){
            map[i][j] = line[j] - '0';
        }
    }

    printf("%d\n", BFS());
}

---

 오랜만에 BFS를 풀이해서 그런가 시간이 많이 걸린 문제였습니다. 일단 시간이 걸리게 된 이유 3가지는 아래였습니다.

 

1. 당연히 arr[curx][cury]이런 식으로 들어갈 줄 알았다

 - input 과정을 생각하지 않은 방식

2. 벽 부순 경우 / 부수지 않은 경우를 어떻게 저장할 것인가

 - 결국 3차원 배열을 통해서 부순 경우 / 부수지 않은 경우를 따로 저장

3. input이 문자열의 형태로 이루어집니다

 - scanf("%d") 형태로 받을 수 없어 string로 해결

 

아이디어는 떠올랐는데 이걸 코드로 표현한다는게 너무 어려웠습니다.