문제 출처

1. 문제설명

  • N*M의 행렬로 표현되는 맵이 있다.
  • 0은 이동할 수 있는 곳, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
  • (1,1)에서 (N,M)까지 이동하려고 한다.
    • 이동하지 않고 같은 칸에 머무르는 게 가능하다.
    • 낮과 밤이 번갈아가면서 등장한다.
      • 처음 이동할 때는 낮이고, 한번 이동할 때마다 낮과 밤이 바뀐다.
      • 이동하지 않고 머무르는 경우에도 낮과 밤이 바뀌게 된다.
    • 만약 이동하는 중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, K개까지 부수고 이동해도 된다.
      • 단, 벽은 낮에만 부술 수 있다.



2. 알고리즘 설계

  • 일반적인 BFS 문제 유형에서 낮과 밤이라는 조건이 추가된 문제이다.
  • N*M 크기의 맵에서 K(1<=K<=10)개의 벽을 부술 수 있는데, 낮과 밤이 추가되었다.
    • bool visited[N][M][K][2]
  • 이동할 수 있는 곳을 탐색해주면서, 벽을 부쉈을 때, 낮일 때, 밤일 때를 각각 체크해주면 된다!



3. 전체 코드

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

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
const int SZ = 1000;

int n, m, k;
char board[SZ][SZ];
bool visited[SZ][SZ][11][2];

typedef struct
{
    int y, x, w, k, state;
} Pos;

int bfs()
{
    queue<Pos> q;
    q.push({0, 0, 1, 0, 1});
    visited[0][0][0][1] = true; // 낮을 1으로

    while (!q.empty())
    {
        Pos cur = q.front();
        q.pop();

        if (cur.y == n - 1 && cur.x == m - 1)
            return cur.w;

        for (int dir = 0; dir < 4; dir++)
        {
            int ny = cur.y + dy[dir];
            int nx = cur.x + dx[dir];
            int nw = cur.w + 1;
            int n_state = !cur.state;

            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;

            if (!visited[ny][nx][cur.k][n_state] && board[ny][nx] == '0')
            {
                q.push({ny, nx, nw, cur.k, n_state});
                visited[ny][nx][cur.k][n_state] = true;
            }

            if (board[ny][nx] == '1' && cur.state && cur.k < k)
            {
                if (!visited[ny][nx][cur.k + 1][n_state])
                {
                    q.push({ny, nx, nw, cur.k + 1, n_state});
                    visited[ny][nx][cur.k + 1][n_state] = true;
                }
            }
        }

        if (!visited[cur.y][cur.x][cur.k][!cur.state])
        {
            q.push({cur.y, cur.x, cur.w + 1, cur.k, !cur.state});
            visited[cur.y][cur.x][cur.k][!cur.state] = true;
        }
    }

    return -1;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> board[i][j];

    cout << bfs();
    return 0;
}



4. 소감

  • BFS 문제에서 조금 유형이 바뀐 문제였다.