[BOJ] 18224 미로에 갇힌 건우

문제 요약

문제 링크: 백준 18224 - 미로에 갇힌 건우

문제 설명

---

접근 방법

큐에 현재 움직임 횟수와, 낮인지 밤인지를 저장해가며 탐색해준다. 낮일 때의 움직임은 0인 좌표에만 1칸씩 이동을 처리해주면 된다.

밤일 때 움직임을 잘 처리해주면 되는데, 주의할 부분은, 방문처리에 대한 부분이다.

같은 좌표더라도 낮/밤 상태와 현재 이동 횟수의 조합을 모두 체크해야 한다.

---

코드

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

int n, m, mat[501][501];
int d[4][2] = { {0,1},{-1,0},{1,0},{0,-1} };
bool vis[501][501][2][11];  // 방문체크는 {y,x} 좌표와 밤or낮, 움직인 횟수(m 최대 10) 

void solve() {
    queue<tuple<int, int, int, int, bool>>q;  // y,x,움직임,날,낮or밤
    q.push({ 0,0,0,1,0 });
    vis[0][0][0][0] = 1;
    while (q.size()) {
        int y = get<0>(q.front());
        int x = get<1>(q.front());
        int move = get<2>(q.front());
        int day = get<3>(q.front());
        bool c = get<4>(q.front());
        q.pop();
        if (y == n - 1 && x == n - 1) {  // 종료조건
            cout << day << (c ? " moon" : " sun");
            return;
        }
        for (int i = 0; i < 4; i++) {
            int yy = y + d[i][0];
            int xx = x + d[i][1];
            if (yy >= n || yy < 0 || xx >= n || xx < 0) continue;
            if (c) {  // 밤의 움직임
                if (mat[yy][xx] == 0) {
                    if (move + 1 == m) {
                        if (vis[yy][xx][!c][0]) continue;
                        q.push({ yy,xx,0,(c ? day + 1 : day),!c });
                        vis[yy][xx][!c][0] = 1;
                    }
                    else {
                        if (vis[yy][xx][c][move + 1]) continue;
                        q.push({ yy,xx,move + 1,day,c });
                        vis[yy][xx][c][move + 1] = 1;
                    }
                }
                else {
                    int dy = yy + d[i][0];
                    int dx = xx + d[i][1];
                    while (1) {
                        if (dy >= n || dy < 0 || dx >= n || dx < 0) break;
                        if (mat[dy][dx] == 0) {
                            if (move + 1 == m) {
                                if (vis[dy][dx][!c][0]) break;
                                q.push({ dy,dx,0,(c ? day + 1 : day),!c });
                                vis[dy][dx][!c][0] = 1;
                            }
                            else {
                                if (vis[dy][dx][i][move + 1]) break;
                                q.push({ dy,dx,move + 1,day,c });
                                vis[dy][dx][c][move + 1] = 1;
                            }
                            break;
                        }
                        dy += d[i][0];
                        dx += d[i][1];
                    }
                }
            }  
            else {  // 낮의 움직임
                if (mat[yy][xx] == 0) {  // 0인 곳만 이동할 수 있다.
                    if (move + 1 == m) {
                        if (vis[yy][xx][!c][0]) continue;
                        q.push({ yy,xx,0,(c ? day + 1 : day),!c });
                        vis[yy][xx][!c][0] = 1;
                    }
                    else {
                        if (vis[yy][xx][c][move + 1]) continue;
                        q.push({ yy,xx,move + 1,day,c });
                        vis[yy][xx][c][move + 1] = 1;
                    }
                }
            }
        }
    }
    cout << -1;
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cin >> mat[i][j];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

마무리

정답률이 낮은 이유가 있는 것 같다는 생각이 드는 문제입니다.

질문게시판의  sdpr 님의 게시글이 도움이 되었습니다.

https://www.acmicpc.net/board/view/100161