0-1 BFS

문제

계기

최근 기존과는 다른 유형의 BFS 문제를 몇 개 만났다.
처음엔 별 생각 없이 예외처리로 풀었다.
그러다 방금 이 문제를 푸는데 불현듯

cost가 적은 것을 먼저 처리해야 하니
queue 앞에 삽입하면 좋겠다. 그러려면 deque를 사용해야겠는데.. 맞나?

이런 생각을 했다.
BFS를 푸는데 deque를 사용한 것은 처음이었다.
일단 만들어 제출한 후, AC를 받고 찾아보니 이게 어디서 주워들었던 0-1 BFS였다.

코드

// 2021.11.09 11:58:04
// 1261 https://boj.kr/1261
#include <bits/stdc++.h>
using namespace std;

const int dy[] = {1, -1, 0, 0};
const int dx[] = {0, 0, 1, -1};
int n, m;
char space[101][101];
bool visited[101][101];

class Node
{
public:
    int y, x, depth;

    bool isInRange()
    {
        return 0 <= y && y < n && 0 <= x && x < m;
    }

    bool isVisited()
    {
        return visited[y][x];
    }

    void visit()
    {
        visited[y][x] = true;
    }
};

int bfs()
{
    deque<Node> q;
    q.push_back({0, 0, 0});
    visited[0][0] = true;

    while (!q.empty())
    {
        Node cur = q.front();
        q.pop_front();

        if (cur.y == n - 1 && cur.x == m - 1)
        {
            return cur.depth;
        }

        for (int i = 0; i < 4; i++)
        {
            int ny = cur.y + dy[i];
            int nx = cur.x + dx[i];
            Node nextNode = {ny, nx, cur.depth};
            if (nextNode.isInRange() && !nextNode.isVisited())
            {
                if (space[ny][nx] == '1')
                {
                    nextNode.depth++;
                    q.push_back(nextNode);
                }
                else
                {
                    q.push_front(nextNode);
                }
                nextNode.visit();
            }
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> m >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> space[i];
    }

    cout << bfs();
}

설명

(우선 문제부터 읽어보자)
벽이 있는 경우에는 cost가 늘어나 후순위로 밀린다.
따라서 cost가 없는 경우에는 (벽을 부수지 않는 경우) 앞에다 삽입한다.
Tree로 생각해보면, 같은 깊이의 정점이 추가되는 느낌이다.
며칠 간 뭔가 불편하고 미심쩍었던 코드가 말끔히 해결되어 시원해서 포스팅을 해봤다. 이상.

결과