[BOJ][골4][14442] 벽 부수고 이동하기2

문제 링크

문제링크

첫 번째 풀이 : 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를 사용했습니다.)

정답 코드

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

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

int arr[MAX][MAX];
int dp[MAX][MAX][11];
bool visited[MAX][MAX][11];
// [i][j][0] : 부수지 않고 이동한 경우 
// [i][j][1] : 부수고 이동한 경우

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

int n, m, kk;
queue<tiii> 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] << " ";
    }
    cout << "\n";
  }
  cout << "========================\n";
}

void bfs(int x, int y) {
  // 지금까지 부신 벽의 갯수, nextx, nexty
  int w, nx, ny;
  int days = 0;
  visited[x][y][0] = true;
  dp[x][y][0] = 1;
  q.push(make_tuple(x, y, 0));
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      tie(x, y, w) = q.front();
      if (x == n - 1 && y == m - 1) {
        cout << dp[x][y][w];
        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]) {
          visited[nx][ny][w] = true;
          dp[nx][ny][w] = dp[x][y][w] + 1;
          q.push(make_tuple(nx, ny, w));
        }
        else if (arr[nx][ny] == 1 && w < kk && !visited[nx][ny][w + 1]) {
          visited[nx][ny][w + 1] = true;
          dp[nx][ny][w + 1] = dp[x][y][w] + 1;
          q.push(make_tuple(nx, ny, w + 1));
        }
      }
    }
  }
  cout << -1;
}

Success Notice: 수고하셨습니다.