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

문제 개요

오늘의 코딩 테스트 문제는 '벽 부수고 이동하기'다. 백준 2206번 문제로, BFS와 상태 관리가 결합된 전형적인 그래프 탐색 문제다.

문제 분석

N×M 크기의 맵에서 (1,1)에서 (N,M)까지 최단 경로로 이동하는 문제다. 0은 이동 가능한 칸, 1은 벽이다. 중요한 점은 딱 한 번 벽을 부술 수 있다는 것이다.

핵심 포인트:

•

기본적으로 BFS로 최단 경로를 찾는다.

•

벽을 한 번 부술 수 있는 옵션이 있다.

•

시작과 도착 지점도 경로에 포함된다.

접근 방식

BFS를 사용하되, 벽을 부쉈는지 여부를 상태로 관리해야 한다. 3차원 배열로 방문 여부를 체크하고, 큐에 벽을 부순 여부도 함께 저장한다.

구현

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

using namespace std;

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

    vector<vector<bool>> map;
    for (int i=0; i<N; i++)
    {
        vector<bool> row;
        string temp;
        cin >> temp;

        for (char c : temp)
            row.push_back((c=='1')?true:false);
        map.push_back(row);
    }

    int level = 0;
    vector<pair<int,int>> oper = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    vector<vector<vector<bool>>> visited(N, vector<vector<bool>>(M, vector<bool>(2, false))); // 0에는 벽 통과 이전, 1에는 벽 통과 이후
    queue<vector<int>> q; // [x, y, 벽통과여부, 단계]
    q.push({0,0,false,1});

    while(!q.empty())
    {
        vector<int> front = q.front();
        q.pop();

        if (front[0]>=N-1 && front[1]>=M-1)
        {
            level = front[3];
            break;
        }

        for (pair<int,int> next : oper)
        {
            int nx = front[0] + next.first;
            int ny = front[1] + next.second;

            // 한칸 이동
            if (nx>=0 && nx<N && ny>=0 && ny<M)
            {
                if (!map[nx][ny] && ((front[2]==0 && !visited[nx][ny][0]) || (front[2]==1 && !visited[nx][ny][0] && !visited[nx][ny][1])))
                {
                    visited[nx][ny][front[2]] = true;
                    q.push({nx, ny, front[2], front[3]+1});
                }
                // 벽을 부술 수 있으면
                if (!front[2] && map[nx][ny] && !visited[nx][ny][1])
                {
                    visited[nx][ny][1] = true;
                    q.push({nx, ny, true, front[3]+1});
                }
            }
        }
    }

    if (level==0)
        level = -1;

    cout << level << endl;

    return 0;
}
C++
복사

주요 로직:

3차원 visited 배열 선언 (x좌표, y좌표, 벽 부순 여부)

BFS 수행

•

큐에 현재 위치, 벽 부순 여부, 이동 거리를 함께 저장

•

4방향 탐색하며 다음 위치가 유효한지 체크

•

벽을 만났을 때 아직 부수지 않았다면 부수고 이동

•

목적지 도달 시 거리 반환

문제 해결 과정

처음에는 DFS로 접근했다가 메모리 초과가 났다. BFS로 전환하고 나서도 방문 처리를 어떻게 할지 고민이 많았다. 결국 3차원 배열을 사용해 벽을 부쉈는지 여부까지 함께 저장하는 방식으로 해결했다.

최적화 과정에서 불필요한 탐색을 줄이기 위해 방문 처리 로직을 개선했다. 벽을 부수지 않은 상태에서 방문한 곳은 벽을 부순 상태에서 다시 방문할 필요가 없다는 점을 활용했다.

회고

이번 문제를 통해 상태를 포함한 BFS 구현 방법과 3차원 배열을 이용한 방문 처리 기법을 익혔다. 그래프 탐색 문제에서 단순히 위치뿐만 아니라 상태도 함께 관리해야 하는 경우가 많다는 걸 다시 한번 상기했다.

개선할 점은 코드의 가독성이다. 현재 구현은 동작하지만, 다른 사람이 봤을 때 이해하기 어려울 수 있다. 변수명을 더 명확하게 짓고, 핵심 로직을 함수로 분리하는 등의 리팩토링이 필요해 보인다.