BOJ 2206 C++

코드

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

string lev[1001];              // 배열 맵 정보를 저장할 lev
int dis[1001][1001];           // 벽을 부수지 않은 경우의 최단 거리를 저장할 dis
int wis[1001][1001];           // 벽을 한 번 부수고 이동한 경우의 최단 거리를 저장할 wis

int dx[4] = {0, 1, -1, 0};     // 방향을 표현하기 위한 배열 dx
int dy[4] = {1, 0, 0, -1};     // 방향을 표현하기 위한 배열 dy

// 새로운 좌표와 벽 정보를 담기 위한 클래스 cord 정의
class cord
{
public:
    int x, y;
    bool wall;
    cord(int _x, int _y, bool _w) : x(_x), y(_y), wall(_w) {}
};

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 이차원 배열의 크기 입력받기
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> lev[i];
    }

    // 최단 거리 배열 dis와 wis 초기화
    for (int i = 0; i < n; i++)
    {
        fill(dis[i], dis[i] + m, -1);
        fill(wis[i], wis[i] + m, -1);
    }

    // 시작 지점의 거리 정보 초기화
    dis[0][0] = 1;
    wis[0][0] = 1;

    // BFS를 수행하기 위한 큐 선언 및 시작 지점 좌표 삽입
    queue<cord> q;
    q.push(cord(0, 0, 1));

    // BFS 시작: 큐가 비어질 때까지 진행
    while (!q.empty())
    {
        auto cur = q.front();
        q.pop();

        // 도착 지점에 도달한 경우 거리 출력 후 종료
        if (cur.y == n - 1 && cur.x == m - 1)
        {
            if (cur.wall == 0)
            {
                cout << wis[cur.y][cur.x];
                return 0;
            }
            else
            {
                cout << dis[cur.y][cur.x];
                return 0;
            }
        }

        // 상하좌우 이동 방향에 대해서 처리
        for (int dir = 0; dir < 4; dir++)
        {
            int nx = dx[dir] + cur.x;
            int ny = dy[dir] + cur.y;
            int nextdis = 0;
            
            if (cur.wall)
                nextdis = dis[cur.y][cur.x] + 1;
            else
                nextdis = wis[cur.y][cur.x] + 1;

            // nx, ny 좌표가 맵의 범위 밖인 경우 생략
            if (nx >= m || nx < 0 || ny >= n || ny < 0)
                continue;

            // 벽을 아직 부수지 않았고 다음 칸이 벽인 경우
            if (cur.wall == 1 && lev[ny][nx] == '1' && wis[ny][nx] == -1)
            {
                wis[ny][nx] = nextdis;
                q.push(cord(nx, ny, 0));
            }    
            // 다음 칸이 빈 칸인 경우
            if (lev[ny][nx] == '0')
            {
                if (cur.wall == 0)
                {
                    if (wis[ny][nx] == -1)
                    {
                        wis[ny][nx] = nextdis;
                        q.push(cord(nx, ny, cur.wall));
                    }
                }
                if (cur.wall == 1)
                {
                    if (dis[ny][nx] == -1)
                    {
                        dis[ny][nx] = nextdis;
                        q.push(cord(nx, ny, cur.wall));
                    }
                }
            }
        }
    }

    // 도착 지점에 도달하지 못한 경우 -1 출력
    cout << -1;
    return 0;
}

설명

벽을 한번만 부순 객체가 이동하는 배열 wis
벽을 하나도 부수지 않은 객체가 이동하는 배열 dis
벽을 부순 객체인지 아닌지 저장하는 wall 변수 좌표를 저장하는 x, y로 이루어진 cord라는 객체를 만들었습니다.

핵심 원리

bfs를 수행하면서 벽을 부순 객체인지 아닌지 확인하여 벽을 부술 수 있으면 wis배열에서 bfs를 수행하게 합니다. 그리고 이 객체의 벽을 부술 수 있는 변수 wall을 0으로 만들어 벽을 다시 못부수게 만듭니다.
벽이 아닌경우에는 일반 bfs처럼 수행합니다.