백준 2206 (벽 부수고 이동하기) / C++

문제 링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

> 풀이

 

bfs를 사용하는 문제입니다.

 

벽을 부수는 횟수가 1회로 한정되어있습니다. 재방문을 방지하기 위해 visited를 많이 사용하는데, 남아있는 부수는 횟수(?) 에 따라 visited를 구분하시면 될 것같습니다.

#include <bits/stdc++.h>
using namespace std;

typedef struct {
        int x;
        int y;
        int cnt;
        int block;
} DEF;

queue<DEF> bfs;
int M, N, MIN = INT_MAX;
int moveX[4] = {0, 0, 1, -1};
int moveY[4] = {1, -1, 0, 0};
bool visited[1001][1001][2];
char graph[1001][1001];

int main(void) {
        scanf("%d %d", &N, &M);
        for (int i = 1; i <= N; i++)
                scanf("%s", &graph[i][1]);
        
        bfs.push({1, 1, 1, 1});
        visited[1][1][1] = true;
        while (!bfs.empty()) {
                auto a = bfs.front();
                int x = a.x, y = a.y, cnt = a.cnt, block = a.block;
                bfs.pop();

                if (x == N && y == M) {
                        MIN = min(MIN, cnt);
                        break;
                }

                for (int i = 0; i < 4; i++) {
                        int nx = x + moveX[i];
                        int ny = y + moveY[i];

                        if (nx >= 1 && nx <= N && ny >= 1 && ny <= M) {
                                if (graph[nx][ny] == '1' && block) {
                                        visited[nx][ny][block - 1] = true;
                                        bfs.push({nx, ny, cnt + 1, block - 1});
                                }

                                if (graph[nx][ny] == '0' && visited[nx][ny][block] == false) {
                                        visited[nx][ny][block] = true;
                                        bfs.push({nx, ny, cnt + 1, block});
                                }
                        }
                }
        }

        if (MIN == INT_MAX) printf("-1");
        else printf("%d", MIN);
}

(개발 환경 : vs code)