[BOJ][골1][16933] 벽 부수고 이동하기3

문제 링크

문제링크

첫 번째 풀이 : BFS

알고리즘

가장 기본적인 BFS를 진행합니다. 그리고 dp를 사용합니다.

• dp[x][y] : 현재까지 오는데 걸린 칸의 수
• dp[nx][ny] = dp[x][y]+1

int sz = q.size()를 사용해서 BFS의 깊이를 측정하는 것이 포인트입니다. 깊이를 측정함으로써 방문했던 곳을 다시 방문하지 않아도 됩니다. 한 번 방문한 곳은 더 이상의 최적 거리가 존재하지 않도록 하여 아래의 두 경우만 다음 좌표로 이동할 수 있습니다.

1. 다음이 0이고 방문하지않은 경우
2. 다음이 1이고 방문하지 않았고 더 부실 수 있는 경우

만약 int sz = q.size()를 사용하지 않으면 아래의 네 가지 경우를 고려해야 합니다. 훨씬 복잡하게 풀어야 합니다.

1. 다음이 0 && 미방문
2. 다음이 0 && 방문 && 더 짧아지는 경우
3. 다음이 1 && 미방문 && 더 부술 수 있음
4. 다음이 1 && 방문 && 더 부술 수 있음 && 더 짧아지는 경우

더 부술 수 있는지 여부를 w < kk를 이용해서 판단합니다.(개인적으로 bfs에서 k를 사용하기 때문에 문제의 k를 받는 변수를 kk를 사용했습니다.)

낮과 밤을 적용할 때는 tuple에 boolean을 하나 추가합니다. isDay를 현재 낮인지 밤이지를 나타내고, !isDay는 다음 날의 낮/밤을 나타냅니다.

정답 코드

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

using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using tiiib = tuple<int, int, int, bool>;
const int MAX = 1001;

int arr[MAX][MAX];
int dp[MAX][MAX][11][2];
bool visited[MAX][MAX][11][2]; // [i][j][부순 벽의 수][if true 낮, otherwise 밤]

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

int n, m, kk;
queue<tiiib> q;
int cnt = 0;

void show(void);
void bfs(int x, int y);

int main()
{
  //freopen("input.txt", "r", stdin);
  //ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m >> kk;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      scanf("%1d", &arr[i][j]);
    }
  }
  if (n == 1 && m == 1) {
    cout << 1;
    return 0;
  }
  bfs(0, 0);
  return 0;
}

void show(void) {
  cout << "============show========\n";
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << dp[i][j][1][0] << " ";
    }
    cout << "\n";
  }
  cout << "========================\n";
}

void bfs(int x, int y) {
  // 지금까지 부신 벽의 갯수, nextx, nexty
  int w, nx, ny;
  bool isDay = true;
  visited[x][y][0][isDay] = true;
  dp[x][y][0][isDay] = 1;
  q.push(make_tuple(x, y, 0, isDay));
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      tie(x, y, w ,isDay) = q.front();
      if (x == n - 1 && y == m - 1) {
        cout << dp[x][y][w][isDay];
        return;
      }
      q.pop();
      for (int k = 0; k < 4; k++) {
        nx = x + dx[k];
        ny = y + dy[k];
        if (nx < 0 || nx >= n) continue;
        if (ny < 0 || ny >= m) continue;
        if (arr[nx][ny] == 0 && !visited[nx][ny][w][!isDay]) {
          visited[nx][ny][w][!isDay] = true;
          dp[nx][ny][w][!isDay] = dp[x][y][w][isDay] + 1;
          q.push(make_tuple(nx, ny, w, !isDay));
        }
        // 현재는 낮(d), 다음은 밤(!d)
        else if (arr[nx][ny] == 1 && w < kk) { // 다음 벽이고 더 부술 수 있고
          if (isDay && !visited[nx][ny][w+1][!isDay]) { // 현재 낮, 미방문
            visited[nx][ny][w + 1][!isDay] = true;
            dp[nx][ny][w + 1][!isDay] = dp[x][y][w][isDay] + 1;
            q.push(make_tuple(nx, ny, w + 1, !isDay));
          }
          else if(!isDay && !visited[nx][ny][w+1][!isDay]){ // 현재 밤, 낮에 오면 미방문인 경우
            visited[x][y][w][!isDay] = true;
            dp[x][y][w][!isDay] = dp[x][y][w][isDay] + 1;
            q.push(make_tuple(x, y, w, !isDay));
          }
        }
      }
    }
  }
  cout << -1;
}

Success Notice: 수고하셨습니다.