BOJ 18224 - 미로에 갇힌 건우

BOJ 18224 - 미로에 갇힌 건우

단순한 BFS에 벽을 넘는 연산을 추가한 것인데,

대개 이런 문제는 DP를 전처리해 가로와 세로로 $1$이 끝나고 처음 나오는 $0$을 $O(1)$에 구할 수 있게 하여 BFS를 돌려야 한다.

근데 은근히 $1$이 많아지면 $0$이 적어지고 $0$이 많아지면 $1$로 넘어가야할 곳이 적어지기 때문에 $N$이 작다면 그냥 전처리를 안하고도 단순히 하나하나 탐색해서 BFS를 돌려줘도 된다.

이 문제를 보고 그렇게 생각했고 600ms 정도로 전처리 없이 통과할 수 있었다.

int dist[501][501][11][2];
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
const int inf = 0x3f3f3f3f;
void solve() {
   memset(dist, inf, sizeof dist);
   int n, m;
   cin >> n >> m;
   vvi b(n, vi(n));
   fv2(b);
   dist[0][0][0][0] = 0;
   queue<array<int, 4>> q;
   q.push({0, 0, 0, 0});
   while (sz(q)) {
      auto [y, x, night, isMoon] = q.front();
      q.pop();

      int nxt_isMoon = night == m - 1 ? isMoon ^ 1 : isMoon;

      for (int d = 0; d < 4; d++) {
         int ny = y + dy[d], nx = x + dx[d];
         if (ny >= 0 && ny < n && nx >= 0 && nx < n && b[ny][nx] == 0) {
            if (dist[ny][nx][md(m, night + 1)][nxt_isMoon] > 1 + dist[y][x][night][isMoon]) {
               dist[ny][nx][md(m, night + 1)][nxt_isMoon] = 1 + dist[y][x][night][isMoon];
               q.push({ny, nx, (int) md(m, night + 1), nxt_isMoon});
            }
         }
      }

      if (isMoon) {
         for (int d = 0; d < 4; d++) {
            for (int k = 1;; k++) {
               int ny = y + dy[d] * k, nx = x + dx[d] * k;
               if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
                  if (b[ny][nx] == 0) {
                     if (dist[ny][nx][md(m, night + 1)][nxt_isMoon] > 1 + dist[y][x][night][isMoon]) {
                        dist[ny][nx][md(m, night + 1)][nxt_isMoon] = 1 + dist[y][x][night][isMoon];
                        q.push({ny, nx, (int) md(m, night + 1), nxt_isMoon});
                     }
                     break;
                  }
               } else break;
            }
         }
      }
   }

   int ans = inf;
   for (int i = 0; i < m; i++) {
      mina(ans, dist[n - 1][n - 1][i][0]);
      mina(ans, dist[n - 1][n - 1][i][1]);
   }
   debug(ans);
   if (ans == inf) cout << -1;
   else {
      cout << ans / (m * 2) + 1 << ' ' << (ans / m % 2 == 0 ? "sun" : "moon");
   }
}