미로만들기

BOJ 미로만들기 2665

SOL)

PQ를 이용하여 푸는 전형적인 문제인거 같은데
잘 몰라서 DP?로 풀었다.

이런 문제를 만나면 PQ를 사용해서 풀도록 해야겠다.

PQ SOL은 가장 적게검은색 칸을 바꾼 녀석들 부터 계산을 하는 것이다.
항상 검은색 칸을 적게 바꾼 녀석들 부터 연산을 하여 끝점에서 연산이 끝나는
녀석이 답이다.

[-] Collapse

#include<cstdio>
#include<algorithm>
const int MAX = 987654321;
int board[52][52], cache[52][52], n;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
void search(int y, int x, int val){
    if (x >= n || y >= n || x < 0 || y < 0) return;
    if (board[y][x] == 0) val++;
    if (y == n - 1 && x == n - 1){
        if (cache[n - 1][n - 1] > val)
            cache[n - 1][n - 1] = val;
        return;
    }
    int& ret = cache[y][x];
    if (ret != MAX && val >= ret) return;
    ret = val;
    for (int i = 0; i < 4; i++)
        search(y + dy[i], x + dx[i], val);
    return;
}
int main(){
    for (int i = 0; i < 52; i++)
    for (int j = 0; j < 52; j++)
        cache[i][j] = MAX;

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        scanf("%1d", &board[i][j]);

    search(0, 0, 0);
    printf("%d", cache[n-1][n-1]);
}