[알고리즘 풀이 분석] BOJ 2206 벽 부수고 이동하기

오늘 해결한 문제는 BOJ 2206 벽 부수고 이동하기 이다!
기본적으로 그래프 탐색 문제이고, BFS를 사용하였으나 기본적인 DFS/BFS 문제에서 약간의 변형이 있는 문제다. 이부분을 해결하는 것이 핵심이었고,, 메모리 초과가 발생해 타 포스팅의 도움을 살짝 받아 해결하였다,,! 아쉽다 ㅜ

BOJ 2206 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입출력

나의 풀이

문제를 읽으며 전형적인 DFS/BFS 문제 + a 문제라고 느꼈다.
하지만 저 알파가 핵심이겠구만,, 싶었고 역시나 그 부분을 해결하는데에 90% 이상의 시간과 노력이 들었다..!

처음엔 '한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면' 이라는 말을 코드로 나타내는 것에 애를 먹었다. '벽을 뚫고 진행했을 때 경로가 더 짧아지는걸 어떻게 판단하지,,?' 라고 계속 붙들고 있었는데,,

생각해보니 어쨌든 BFS로 모든 경우의 수가 다 커버되기 때문에 벽을 뚫던 안뚫던 최소 경로 값으로 갱신되기만 하면 해결되고 사전에 경로가 짧아질지 안짧아질지 판단할 필요는 없는 것 같았다!

결국 '한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면' 가 중요한게 아니고, 그냥 한번은 뚫을 수 있다는 게 핵심이었던 것이다!!

이후에는 queue에 들어갈 자료형을 구조체로 따로 정의했다. Location 이라는 이름의 구조체를 정의하고, 구조체에는 현재 가리키고 있는 지도상의 위치 (row, col)와 현재까지 경로 이동 값 cost, 벽을 부수고 왔는지 아닌지를 나타내는 값 broken 이 들어가 있게 했다.

typedef struct location{
    pair<int, int> point;
    int cost;
    bool broken;

    location(pair<int, int> p, int c, bool b){
        this->point = p;
        this->cost = c;
        this->broken = b;
    }
}Location;

현재 위치를 기준으로 4방향을 탐색해서 들어갈 수 있으면 Location 구조체를 queue에 넣어가면서 BFS 를 진행해서 코드를 작성했다. 주어진 테스트 케이스는 잘 통과 했는데 채점 과정에서 메모리 초과가 발생했다!

기본적인 알고리즘 자체는 문제가 없을 것 같은데 메모리 초과가 났다면 구조체 문제가 아닐까 짐작했고, 질문 리스트를 보니 나처럼 구조체를 정의해서 작성하신 분도 메모리 초과가 떴길래, 구조체를 사용하지 않는 방식으로 다시 코드를 수정했다! (여기서 약간 한계가 왔다 ㅋ,,)

하지만 아이디어가 잘 떠오르지 않았는데 찾아보니 3차원 배열을 이용한 경우가 많이 있는 것 같았다! 방문 체크를 하는 배열을 3차원으로 선언해서 지도의 각 지점마다 뚫고 갔을 때, 안뚫고 갔을 때를 구분하여 경로 값으로 채우는 방식이었다. 3차원 배열 값을 0으로 세팅 해 두고 방문 했다면 경로 값은 무조건 1보다 크기 때문에 방문 여부 체크도 함께 할 수 있도록 했다!

3차원 배열을 사용하여 문제를 해결하였고 결국 통과했다!!

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>

// BOJ 2206 벽 부수고 이동하기, BFS 심화 골드 4
using namespace std;

int MINCOST = 2147483647;

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

bool findMinWay(int N, int M, vector<vector<int>> map) {
    bool found = false;  // 반환값, 최소 경로를 찾았는지를 확인 
    vector<vector<vector<int>>> visited(N, vector<vector<int>>(M, vector<int>(2,0)));
    queue<pair<pair<int,int>, int>> q;

    q.push(make_pair(make_pair(0,0), 0));
    visited[0][0][0] = 1;
    visited[0][0][1] = 1;

    while (!q.empty()){
        pair<pair<int, int>, int> loca = q.front();
        q.pop();

        // 도착 지점이라면, 처음 도달한거면 경로를 찾았음을 저장하고, 최소 경로 값인지 확인 
        if(loca.first.first == N-1 && loca.first.second == M-1){
            if (!found) found = true;
            if (MINCOST > visited[loca.first.first][loca.first.second][loca.second]){
                MINCOST = visited[loca.first.first][loca.first.second][loca.second];
            }
            continue;
        }

        // 그 외 지점이라면 
        for (int i = 0; i < 4; ++i) {
            int row = loca.first.first + dy[i];
            int col = loca.first.second + dx[i];

            // 상하좌우 4 방면으로 확인 
            if(row>=0 && row<N && col>=0 && col<M){ // 지도 내 범위 
                if (map[row][col] == 0){  // 기존에 뚫었던 안뚫었던 갈 수 있는 칸이라면
                    if(visited[row][col][loca.second] == 0) {  // 처음 방문이면 
                        
                        // loca.second : 뚫어서 온건지, 안뚫고 온건지
                        q.push(make_pair(make_pair(row, col), loca.second));
                        visited[row][col][loca.second] = visited[loca.first.first][loca.first.second][loca.second] + 1;
                    }
                }else{  // 벽을 만나면 
                    if (loca.second == 0){  // 뚫지 않고 온거면 
                        
                        // 이제 뚫는 거니까 visited 3번째 index = 1 
                        visited[row][col][1] = visited[loca.first.first][loca.first.second][loca.second] + 1;
                        q.push(make_pair(make_pair(row, col), 1));
                    }
                }
            }
        }
    }

    return found;
}

int main() {
    int N, M;
    cin>>N>>M;

    vector<vector<int>> map(N, vector<int>(M, 0));

    string row;
    for (int i = 0; i < N; ++i) {
        cin>>row;
        for (int j = 0; j < M; ++j) {
            if (row[j] == '1'){
                map[i][j] = 1;
            }
        }
    }

    if (findMinWay(N, M, map)){
        cout<<MINCOST<<'\n';
    }else{
        cout<<-1<<'\n';
    }

    return 0;
}

난이도를 조금 높였을 뿐인데 쉽지 않았다..!🥲
더 많이 풀어보자!!! 화이팅~!

[BOJ 2206] 벽 부수고 이동하기 (Python)