2665번 미로만들기

https://www.acmicpc.net/problem/2665

 

 

처음에는 단순 queue로 구현했다가, 예제 1번의 답이 계속 5로 나왔다.

 

문제를 잘 읽어보면

 

검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

 

라고 쓰여있는데, 이는 '검은 방'은 최대한 피해서 가야한다는 의미이다.

 

즉, 검은 방과 흰 방 중 우선순위가 더 높은 방은 흰 방이다.

 

이 부분에서 힌트를 얻어, queue말고 deque로 구현한다.

 

다음에 이동할 방이 검은 방 → deque의 맨 뒤(우선순위가 낮으므로)

다음에 이동할 방이    흰 방 → deque의 맨 앞(우선순위가 높으므로)

 

 

#include <bits/stdc++.h>

using namespace std;

#define MAX 55

int n, m[MAX][MAX];
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
bool used[MAX][MAX];

int bfs()
{
    int ret = INT32_MAX;

    deque<tuple<int, int, int> > dq;
    dq.push_back({ 0, 0, 0 });
    used[0][0] = true;

    while (!dq.empty())
    {
        int dqs = dq.size();

        while (dqs--)
        {
            int r, c, b;
            tie(r, c, b) = dq.front();

            dq.pop_front();

            if (r == n - 1 && c == n - 1) {           
                ret = min(ret, b);
            }

            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];

                if (y < 0 || y >= n || x < 0 || x >= n || used[y][x]) {
                    continue;
                }
                
                used[y][x] = true;

                // 검은 방
                if (m[y][x] == 0) {
                    dq.push_back({ y, x, b + 1 });
                }
                else {
                    dq.push_front({ y, x, b });
                }
            }
        }
    }

    return ret;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &m[i][j]);
        }
    }

    printf("%d\n", bfs());

    return 0;
}