백준 1600번 - 말이 되고픈 원숭이

백준 1600번 - 말이 되고픈 원숭이

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

이 문제는 BFS 알고리즘을 사용한 문제였다.

결론부터 얘기하면 3차원 배열을 사용하는 문제였다.

처음에 2차원 배열로 BFS 구현 후 horse란 배열을 따로 만들어 놓고 말의 움직임을 체크해 놓았었는데

이렇게 구현해 보니 당연히 틀렸습니다...

이유는 아래와 같은 테스트 케이스였다.

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

ans : 6

 

이 테스트 케이스를 보면 3행 4열까지 한 번의 움직임(원숭이의 움직임)으로 가다가 마지막에 한 번만

말의 움직임으로 가면 6의 답을 얻을 수 있다.

나는 2차원 배열로 구현했을 때 말 이동 횟수를 초과할 시 더 이상 말의 움직임을 할 수 없게 구현해서

계속 답이 0이 나와 틀렸었다.

 

다시 3차원 배열로 짜 보니 그래도 틀렸습니다..

이유는 check배열의 크기가 문제였다.. 정말 크기가 1만 작아도 틀리니 항상 주의해야겠다.

3차원 배열로 만들고 각 칸에 말의 이동 횟수의 모든 경우의 수를 저장하고

도착 칸의 모든 경우의 수를 확인하며 가장 최소의 경우의 수를 찾는 방식으로 문제를 해결했다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <tuple>
#pragma warning(disable:4996)
using namespace std;
 
int K, w, h;
int map[201][201];
int dis[201][201][31];
bool check[201][201][31] = { false };
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int fx[8] = { -2,-1,1,2,2,1,-1,-2 };
int fy[8] = { 1,2,2,1,-1,-2,-2,-1 };
 
void bfs() {
    queue < tuple<int, int, int>>q;
    q.push(make_tuple(0, 0, 0));
    check[0][0][0] = true;
    while (!q.empty()) {
        int x, y, k;
        tie(x, y, k) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if ((0 <= nx && nx < h) && (0 <= ny && ny < w) && map[nx][ny] != 1) {
                if (check[nx][ny][k] == false) {
                    check[nx][ny][k] = true;
                    dis[nx][ny][k] = dis[x][y][k] + 1;
                    q.push(make_tuple(nx, ny, k));
                }
            }
        }
        for (int i = 0; i < 8; i++) {
            int nx = x + fx[i];
            int ny = y + fy[i];
            if ((0 <= nx && nx < h) && (0 <= ny && ny < w) && k + 1 <= K) {
                if (check[nx][ny][k + 1] == false && map[nx][ny] != 1) {
                    check[nx][ny][k + 1] = true;
                    dis[nx][ny][k + 1] = dis[x][y][k] + 1;
                    q.push(make_tuple(nx, ny, k + 1));
                }
            }
        }
    }
}
 
int main() {
    scanf("%d", &K);
    scanf("%d %d", &w, &h);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    memset(dis, 0, sizeof(dis));
    bfs();
    int ans = 10000000;
    bool flag = false;
    for (int i = 0; i <=K ; i++) {
        if (dis[h - 1][w - 1][i] == 0 && check[h - 1][w - 1][i] == false)continue;
        flag = true;
        ans = min(ans, dis[h - 1][w - 1][i]);
    }
    if (flag == false) printf("-1\n");
    else printf("%d\n", ans);
}

 

참고로 3차원 배열을 사용하기 위해 tuple을 사용했다.

아래는 몇 가지 테스트 케이스이다. 이 테스트 케이스를 다 통과하면 웬만하면 맞았습니다를 받을 수 있을 것이다ㅎㅎ

(모든 테스트 케이스는 백준 질문 검색 게시판에 있는 케이스들입니다.)

 

3
4 5
0 1 1 1
1 1 0 1
1 1 1 1
1 1 1 0
1 1 1 0
ans 3

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0
ans 6

5
1 1
0
ans 0

1
3 4
0 0 0
1 1 0
1 1 1
1 0 0
ans 5