[BOJ/16939/C++] 벽 부수고 이동하기 3

출처:https://www.acmicpc.net/problem/16933

문제

• N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.

• 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

조건

• 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.

• 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.

• 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

풀이

저번에 벽 부수고 이동하기 2에서 짯던 코드는 내가 의도한대로 짠 코드가 아니였지만, 운좋게 맞아떨어진 케이스 였다. 벽일 때만 현재 깬 벽의 갯수를 저장하고 있는 방문배열에 저장을 해주어야 했는데, 약간 모든 방문배열을 통일적으로 운영하는 느낌으로 짯던것 같다.

방문배열[x][y][0]이면 벽을 0개 깼을 때, [x][y][1]이면 벽을 1개 깼을 때로 유도했는데, board[x][y] ==0인 경우에는 벽이 없더라도 일단 벽을 깰 수 있으면, [x][y][1]에 저장하는 형태로 코드를 작성했었다. 그래서, 코드를 조금 더 조건을 직관적으로 바꾸어서, 벽이 있고, 벽을 깰 수 있으면서, 해당 방문좌표에 방문을 안했으면,과 같이 조건을 하나하나 명시 해주는 방식으로 코드를 짰다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int N, M, K;

struct Point
{
  int x;
  int y;
  int Wall;
  int dist;
  bool IsNoon;
};

int board[1001][1001];
bool visited[1001][1001][10];

bool outOfRange(int x, int y)
{
  return (x < 0 || x >= N || y < 0 || y >= M);
}

void solve()
{
  queue<Point> Q;
  for (int i = 0; i < K; i++)
  {
    visited[0][0][i] = true;
  }
  Q.push({0, 0, 0, 1, true});

  while (!Q.empty())
  {
    Point cur = Q.front();
    Q.pop();
    if (cur.x == N - 1 && cur.y == M - 1)
    {
      cout << cur.dist << '\n';
      return;
    }
    for (int dir = 0; dir < 4; dir++)
    {
      int nx = cur.x + dx[dir];
      int ny = cur.y + dy[dir];
      if (outOfRange(nx, ny))
        continue;
      // 낮이어서 벽을 부술 수 있고, 해당 점에 방문을 안했을 경우
      if (board[nx][ny] == 1 && cur.Wall < K && !visited[nx][ny][cur.Wall + 1])
      {
        // 낮
        if (cur.IsNoon)
        {
          visited[nx][ny][cur.Wall + 1] = true;
          Q.push({nx, ny, cur.Wall + 1, cur.dist + 1, !cur.IsNoon});
        }
        // 밤
        else
        {
          Q.push({cur.x, cur.y, cur.Wall, cur.dist + 1, !cur.IsNoon});
        }
      }
      else if (board[nx][ny] == 0 && !visited[nx][ny][cur.Wall])
      {
        visited[nx][ny][cur.Wall] = true;
        Q.push({nx, ny, cur.Wall, cur.dist + 1, !cur.IsNoon});
      }
    }
    // 벽을 부술 수 있는 횟수가 남은 경우
  }
  cout << -1 << '\n';
  return;
}

int main()
{
  fastio;
  cin >> N >> M >> K;

  string s;
  for (int i = 0; i < N; i++)
  {
    cin >> s;
    for (int j = 0; j < M; j++)
    {
      board[i][j] = s[j] - '0';
    }
  }
  solve();
  return 0;
}