백준 1600번 말이 되고픈 원숭이 (C++)

문제 링크 : https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

문제 요약

 

1. 원숭이는 왼쪽 맨 위칸에서 오른쪽 맨 아래칸으로 최소한의 움직임으로 이동하고 싶습니다. 

2. 말의 움직임, 또는 인접한 4방위 움직임을 통해 원숭이는 이동할 수 있습니다.

3. 말의 움직임으로 이동해도, 4방위로 이동해도, 모두 이동 횟수는 1회 입니다.

4. 말의 움직임으로 이동할 경우, 원숭이는 장애물을 뛰어넘을 수 있습니다. 하지만 장애물에 도착할 수는 없습니다.

 

핵심 포인트

 

말의 움직임과 4방위 움직임이라는 2가지 이동 방식이 있습니다.

두 움직임이 겹치지 않도록 방문 여부를 체크하는게 핵심입니다.

때문에 방문 여부를 체크하는 bool문은 3차원 배열로 선언합니다.

방문여부 배열의 예시는 아래와 같은 값을 가지면 됩니다.

bool ch[h+1][w+1][k+1]

 

문제 풀이

 

1. k,h,w의 값을 입력 받고 해당 배열을 선언합니다.

벡터의 동적할당을 활용해도 무방하고 일반적인 배열을 선언해도 무방합니다.

    int k,h,w;
    cin >> k;
    cin >> w >> h; // 가로와 세로 순으로 입력
    vector<vector<int>> v(h+1,vector<int>(w+1,0));
    vector<vector<vector<bool>>> ch(h+1,vector<vector<bool>>(w+1,vector<bool>(k+1,false)));
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++) cin >> v[i][j];
    }

 

2. 구조체로 큐에 들어갈 변수들을 선언합니다. 그리고 큐를 선언하고 큐에 값을 넣어줍니다.

// 전역 변수
struct monkey{
    int move,horse;
    int yy, xx;
};

int m,hs,y,x,nm,ny,nx,my[]={-1,-2,-2,-1,1,2,2,1,1,0,-1,0},mx[]={-2,-1,1,2,2,1,-1,-2,0,-1,0,1}; // 앞 8개는 체스 말, 뒤 4개는 인접한 사방위

    /// int main() 함수
    ...
    queue<monkey> q;
    q.push({0,0,1,1});
    ch[1][1][0] = true; // 방문 표시

이때 방문여부를 판단하는 bool문 배열은 3차원으로 구현해야합니다.

원숭이가 제한된 k번 이내에 말의 움직임으로 이동하는 움직임은 별도로 체크해줘야하기 때문입니다.

만약 3차원으로 구현하지 않고 2차원으로 구현할 경우, 말의 움직임으로 이미 방문한 지역을 4방위로 접근하지 못해, 정답에 접근할 수 없는 경우가 발생할 수 있습니다.

 

3. 다음은 while문의 내부 구조입니다.

    while(!q.empty()){
        m = q.front().move; // 1
        hs = q.front().horse;
        y = q.front().yy;
        x = q.front().xx;
        q.pop();
        if(y==h&&x==w){ // 2
            cout << m << "\n";
            exit(0);
        }
        for(int i=0; i<12; i++){ // 3
            if(hs==k&&i<8) continue; // 4
            ny = y+my[i]; // 5
            nx = x+mx[i];
            if(ny<=0||ny>h||nx<=0||nx>w) continue; // 6
            if(v[ny][nx]==1) continue; // 7
            if(i<8){ // 8
                if(hs+1>k) continue; // 8-1
                if(ch[ny][nx][hs+1]) continue; // 8-2
                ch[ny][nx][hs+1] = true; // 8-3
                q.push({m+1,hs+1,ny,nx});
            }
            else{ // 9
                if(ch[ny][nx][hs]) continue; // 9-1
                ch[ny][nx][hs] = true; // 9-2
                q.push({m+1,hs,ny,nx});
            }
        }
    }

(1) 큐의 맨 앞에 위치한 값들을 변수에 저장합니다.

(2) 만약 현재 위치가 목표 지점일 경우, 누적 움직임 횟수를 출력하고 종료합니다.

(3) 그렇지 않을경우 0~12미만까지 for문을 진행합니다. 0~7까지는 말의 움직임을 의미하고, 8~11은 4방위의 움직임을 뜻합니다.

(4) 만약 누적 말의 움직임 횟수가 k번이고, 현재 움직이려는 방식이 말의 움직임일 경우 continue를 합니다.

(5) 움직이려는 방식의 값을 갱신해줍니다.

(6) 새로 갱신된 위치가 이동가능 범위를 넘어설경우 continue를 합니다.

(7) 새로 갱신된 위치가 장애물일경우 continue를 합니다.

(8) 만약 말의 움직임으로 새로이 이동한거라면...

-> (8-1) 현재 말의 움직임 횟수 + 1아 k를 초과한다면 continue를 합니다.

-> (8-2) 새로 움직이려는 위치를 이미 방문했다면 continue를 합니다.

-> (8-3) 위의 두 케이스를 통과할 경우, 새로 갱신된 위치를 방문표시해주고 큐에 삽입합니다.

(9) 만약 4방위의 움직임으로 새로이 이동한거라면...

-> (9-1) 새로 움직이려는 위치를 이미 방문했다면 continue를 합니다.

-> (9-2) 그렇지 않을 경우, 방문 표시를 해주고 큐에 삽입합니다.

 

4. while문을 빠져나갈 경우, 정답을 구할 수 없다는 뜻이므로 -1을 출력한다.

#include <iostream>
#include <algorithm>
#include <vector> 
#include <queue>
using namespace std;

struct monkey{
    int move,horse;
    int yy, xx;
};

int m,hs,y,x,nm,ny,nx,my[]={-1,-2,-2,-1,1,2,2,1,1,0,-1,0},mx[]={-2,-1,1,2,2,1,-1,-2,0,-1,0,1}; // 앞 8개는 체스 말, 뒤 4개는 인접한 사방위

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int k,h,w;
    cin >> k;
    cin >> w >> h;
    vector<vector<int>> v(h+1,vector<int>(w+1,0));
    vector<vector<vector<bool>>> ch(h+1,vector<vector<bool>>(w+1,vector<bool>(k+1,false)));
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++) cin >> v[i][j];
    }
    queue<monkey> q;
    q.push({0,0,1,1});
    ch[1][1][0] = true;
    while(!q.empty()){
        m = q.front().move;
        hs = q.front().horse;
        y = q.front().yy;
        x = q.front().xx;
        q.pop();
        if(y==h&&x==w){
            cout << m << "\n";
            exit(0);
        }
        for(int i=0; i<12; i++){
            if(hs==k&&i<8) continue;
            ny = y+my[i];
            nx = x+mx[i];
            if(ny<=0||ny>h||nx<=0||nx>w) continue;
            if(v[ny][nx]==1) continue;
            if(i<8){
                if(hs+1>k) continue;
                if(ch[ny][nx][hs+1]) continue;
                ch[ny][nx][hs+1] = true;
                q.push({m+1,hs+1,ny,nx});
            }
            else{
                if(ch[ny][nx][hs]) continue;
                ch[ny][nx][hs] = true;
                q.push({m+1,hs,ny,nx});
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}