[C++] 백준 2665번: 미로 만들기

www.acmicpc.net/problem/2665

2665번: 미로만들기

첨에 어떻게 접근할 지 고민하다가 방금 푼 문제였던 벽 부수고 이동하기의 코드를 활용해서 풀었다.

 

사실 최솟값이 필요없기 때문에 좀 비효율적으로 코드를 짠 것 같아서 좀 아쉽다..

 

다음에 풀 때는 그 전의 바꾼 방갯수를 비교해서 최신화하는 식을 짜봐야겠다..

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;

struct map {
    int x, y, w;
};

int n, ans = -1;
int a[51][51];
int dist[51][51][100];
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };

int bfs(int b) {
    queue<map> q;
    q.push({ 0, 0, 0 });
    dist[0][0][0] = 1;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int w = q.front().w;
        q.pop();
        if (x == n - 1 && y == n - 1) {
            return dist[x][y][w];
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (dist[nx][ny][w]) continue;
            if (a[nx][ny] == 1) {
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({ nx, ny, w });
            }
            if (a[nx][ny] == 0 && w < b) {
                dist[nx][ny][w+1] = dist[x][y][w] + 1;
                q.push({ nx, ny, w+1 });
            }
        }
    }
    return -1;
}

int main() {
    int b = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &a[i][j]);
        }
    }
    while (1) {
        ans = bfs(b);
        if (ans >= 0) {
            printf("%d", b);
            break;
        }
        else {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k <= b; k++) {
                        dist[i][j][k] = 0;
                    }
                }
            }
        }
        b++;
    }
    return 0;
}