BOJ 1600 (말이 되고픈 원숭이)

📃 문제

문제링크
개인적으로 벽 부수고 이동하기 와 비슷한 문제였다. (둘다 처음에 못푼건 🥲)

---

📖 풀이

처음 풀이를 생각할 때 bfs 를 3차원 배열 [20][20][1] 을 돌면서,
말의 능력을 사용한 횟수를 count 하면 풀 수 있지 않을까? 라고 생각했다.

하지만 단순하게 vis 배열을 2차원으로 선언하고 vis 가 1인 곳을 다시 방문하지 못하게 설정하면

0	0	0	0
1	1	0	1
1	1	1	1
0	0	0	0

위와 같은 case 에서 도착점에 도달할 수 없게되는 문제가 발생한다.

그럼 방문했던 곳도 말의 능력을 쓴 case 에 따라서 다시 방문 할 수 있도록 설정해야 하는데 이를 어떻게 처리할 수 있을까?

K 의 최대값이 30 이기 때문에 [20][20][30] 3차원 배열을 통해서 현재 위치에 몇번의 능력을 쓰고 왔는지까지 모두 vis 배열로 count 해주면 된다!

1. 공간복잡도

   1 ) 능력 횟수에 따른 vis , 최단거리 저장할 int [20][20][30]
   2 ) 현재 장애물 위치를 저장할 배열 int[20][20]

메모리 제한이 256MB 이므로, 약 0.6억개의 int 를 사용할 수 있다.
1.2 x 10^4 + 4 x 10^2 으로 메모리 초과는 발생하지 않는다.

2. 시간복잡도

   3차원 배열 bfsO(20*20*30)

사실상 2차원 배열을 말이 능력을 쓴 횟수에 맞게 차원을 늘려서 계산해주기 때문에 20*20*30 크기의 배열을 bfs 도는것과 동일하다.

---

🖥 코드

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int w,h,k;
int board[202][202];
int answer[202][202][32];
bool vis [202][202][32];
int dy[4] = {-1, 1, 0 ,0};
int dx[4] = {0, 0, -1, 1};
int dy2[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dx2[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

int main(void) {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k;
    cin >> w >> h;
    for(int y = 0; y < h; y++)
        for(int x = 0; x < w; x++)
            cin >> board[y][x];
    
    queue<pair <pair<int, int>, int> >q;
    //Case 1
    if(board[0][0] == 1){
        cout << -1;
        return 0;
    }

    q.push({{0, 0}, 0}); //Starting Point
    vis[0][0][0] = 1;

    while(!q.empty()) {

        pair<int,int> cur = q.front().first; // monkey's pos
        int cnt = q.front().second; // horse
        q.pop();

        if(cnt < k) {
            for(int dir = 0; dir < 8; dir ++){
                int ny = cur.first + dy2[dir];
                int nx = cur.second + dx2[dir];
                if(ny < 0 || ny >= h || nx <0 || nx >= w)continue;
                if(vis[ny][nx][cnt + 1])continue;
                if(board[ny][nx] == 1)continue;
                q.push({{ny, nx}, cnt + 1});
                vis[ny][nx][cnt + 1] = 1;
                answer[ny][nx][cnt + 1] = answer[cur.first][cur.second][cnt] + 1;
            }
        }

        for(int dir = 0; dir < 4; dir ++) {
            int ny = cur.first + dy[dir];
            int nx = cur.second + dx[dir];
            if(ny < 0 || ny >= h || nx <0 || nx >= w)continue;
            if(vis[ny][nx][cnt])continue;
            if(board[ny][nx] == 1)continue;
            q.push({{ny, nx}, cnt});
            vis[ny][nx][cnt] = 1;
            answer[ny][nx][cnt] = answer[cur.first][cur.second][cnt] + 1;
        }

    }

    int min = 2140000000;

    if(w == 1 && h == 1){
        cout << 0;
        return 0;
    }

    for(int i = 0; i <= k; i++){
        if(answer[h - 1][w - 1][i] == 0)continue;
        else if(answer[h - 1][w - 1][i] <= min)min = answer[h - 1][w - 1][i];
    }
    
    if(min == 2140000000) cout << -1;
    else cout << min;

    
    return 0;
}

---

🔨 피드백

처음 문제를 보자마자 벽 부수고 이동하기랑 비슷하다는걸 알았지만, 정답 풀이를 떠올리는데 까지는 시간이 좀 걸렸다. (ㅠ)

그리고, 계속 100% 에서 틀렸습니다. 받았다.

1
1 1
0

에 대한 예외 처리를 해주지 않았다.
bfs 를 돌고나서, [h - 1][w - 1][i] 값들을 for 문 돌면서 확인할 때,

if(answer[h - 1][w - 1][i] == 0)continue;

에 대한 처리를 통해서, 문제를 해결할 수 있었다.

최근에 교육을 듣는다는 핑계로 ps 를 소홀히 했던것 같다. 매일 한 문제씩 풀 자신은 없지만 다시 코테 스터디도 병행하면서 일주일에 적어도 4문제씩은 풀어서 정리해야 겠다!🔥🔥