[C++] 백준 1600 : 말이 되고픈 원숭이

백준 1600 : 말이 되고픈 원숭이

 

문제 링크

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

 

문제 내용

 같은 이동 방식을 가진다. 다음 그림에 말의 이동 방법이 나타나 있다. x 표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.

근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.

이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야 한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.

 

 

Idea

(시행착오...)

bfs긴 bfs문제이긴 한데 접근하는 방법이 어려웠다. 원숭이가 먼저 말처럼 K번을 모두 움직인 후 원숭이처럼 가는 것도 아니고 최대였기 때문에 무빙 방법에 제약이 없었기 때문이다.

일단, 처음엔 평범한 bfs처럼 코딩을 했다. horse란 변수와 이차원 배열인 visit를 가지고 말처럼 가는 8방향과 원숭이가 가는 4방향으로 짰다. 그러나 이 방법은 말처럼 움직이는 방식을 제대로 count 해주지 못할 뿐만 아니라 제대로 목적지에 도달하지 못할 경우도 존재했다.

 

(풀이)

그래서 visit를 3차원 배열로 바꿔서 말 처럼 움직이는 것을 count 해주기로 하였다.

visit[x][y][z]

• x : 세로줄 좌표
• y : 가로줄 좌표
• z : 말처럼 움직인 횟수

기존의 큐 자료형에도 변화를 주었다. 구조체(line 9 ~ line 13)를 이용하여 좌표와 말처럼 움직인 횟수를 기록할 수 있는 큐(line 31)를 만들어 사용하였다.

 

이 풀이의 알고리즘은 다음과 같다.

[초기화]

• 장애물이 있는 부분은 -1로 바꾼다.
• 즉, 기존 배열에 +1을 하여 움직인 횟수를 계산한다.

 

[bfs]

해당 좌표에 방문하면 그 좌표에 대해 무조건 true가 아닌 '좌표+말 이동 횟수'를 모두 결합하여 true 여부를 결정한다. 

1. 큐에서 좌표와 말의 이동 횟수를 뽑는다.(line 38 ~ line 41)
2. 만약, 말의 이동 횟수가 K보다 작다면 말처럼 움직인다.(line 45 ~ line 58)
3. 만약, 움직인 좌표가 도착지점이라면 횟수를 출력하고 종료한다.(lien 61 ~ line 64)
4. 원숭이처럼 움직인다.(line 70 ~ line 81)
5. 만약, 움직인 좌표가 도착지점이라면 횟수를 출력하고 종료한다.(line 84 ~ line 87)
6. bfs를 탈출 했다면 도착지점에 도달하지 못했음을 의미한다.

 

 

Code

#include <stdio.h>
#include <queue>
using namespace std;
 
int arr[200][200];
bool visit[200][200][32];
int k, w, h;
 
typedef struct {
    int x;
    int y;
    int horse;
}st;
 
//각각 말과 원숭이가 움직일 수 있는 좌표
int h_move[][2] = { {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1} };
int m_move[][2] = { {1,0},{0,1},{-1,0},{0,-1} };
 
int main() {
    scanf("%d %d %d", &k, &w, &h);
 
    //장애물이 있는 곳은 -1
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            scanf("%d", &arr[i][j]);
            if (arr[i][j]) arr[i][j] = -1;
        }
    }
 
    //구조체를 자료형으로 큐를 만듦
    queue<st> q;
    q.push({ 0,0,0 });
    visit[0][0][0] = true;
    int nx, ny;
 
    //bfs
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int horse = q.front().horse;
        q.pop();
 
        //말 처럼 움직인 것이 K번 미만일 때
        //말 처럼 움직이기
        if (horse < k) {
            //8방향으로
            for (int i = 0; i < 8; i++) {
                nx = x + h_move[i][0];
                ny = y + h_move[i][1];
 
                //범위 내 좌표면서 장애물이 아니고 방문한 곳이 아니라면
                if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                    if (arr[nx][ny] != -1 && !visit[nx][ny][horse + 1]) {
                        visit[nx][ny][horse + 1] = true;
                        arr[nx][ny] = arr[x][y] + 1;
                        q.push({ nx,ny,horse + 1 });
                    }
                }
 
                //도착한 좌표가 도착지점(오른쪽 아래)일 경우
                if (nx == h - 1 && ny == w - 1) {
                    printf("%d\n", arr[nx][ny]);
                    return 0;
                }
            }
        }
 
        //원숭이 처럼 움직이기
        //4방향으로
        for (int i = 0; i < 4; i++) {
            nx = x + m_move[i][0];
            ny = y + m_move[i][1];
 
            //범위 내 좌표면서 장애물이 아니고 방문한 곳이 아니라면
            if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                if (arr[nx][ny] != -1 && !visit[nx][ny][horse]) {
                    visit[nx][ny][horse] = true;
                    arr[nx][ny] = arr[x][y] + 1;
                    q.push({ nx,ny,horse });
                }
            }
 
            //도착한 좌표가 도착지점(오른쪽 아래)일 경우
            if (nx == h - 1 && ny == w - 1) {
                printf("%d\n", arr[nx][ny]);
                return 0;
            }
        }
    }
    /*bfs문을 탈출했다면 목적지에 도달하지 못했다는 것*/
 
    //출발지점과 도착지점이 같다면 0
    //아니라면 -1
    if (w == 1 && h == 1) printf("0\n");
    else printf("-1\n");
    return 0;
}