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

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

1600번: 말이 되고픈 원숭이

BFS 문제입니다.

문제 조건

 

출력 예시

 

문제 접근 방법

1. 4방향 탐색과, 말로 이동할 수 탐색을 만든다.

2. BFS를 통해, 말로 이동할때와, 4방향으로 탐색할때를 모두 확인한다.

3. 도착점의 좌표를 확인해 최솟값을 찾는다.

 

 

문제 접근 방법 - 2번

while (!q.empty()) {
        int x1 = q.front().x;
        int y1 = q.front().y;
        int k1 = q.front().use_k;
        q.pop();
        if (k1 < K) {
            for (int i = 0; i < 8; i++) {
                int xx = x1 + horse_x[i];
                int yy = y1 + horse_y[i];
                if (xx >= 1 && yy >= 1 && xx <= H && yy <= W) {
                    if (check[xx][yy][k1+1] == 0 && monkey[xx][yy] == 0) {
                        check[xx][yy][k1 + 1] = check[x1][y1][k1] + 1;
                        q.push({ xx, yy, k1 + 1 });
                    }
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= H && yy <= W) {
                if (check[xx][yy][k1] == 0 && monkey[xx][yy] == 0) {
                    check[xx][yy][k1] = check[x1][y1][k1] + 1;
                    q.push({ xx, yy, k1 });
                }
            }
        }
    }

똑같은 좌표라도 도착할 수 있는 방법이 2가지가 있습니다.

1. 4방향 탐색만을 사용해서 왔을때

2. 말처럼 이동하고 왔을때

이때, 같은 좌표라도 1번, 2번 방법으로 온 것은 차이가 큽니다.

따라서 해당 좌표에 말처럼 몇번 이동하고 왔는지를 저장하는 check 배열을 만들었습니다.

말처럼 이동한 횟수가 K번보다 작을때, 말처럼 이동해주는 것을 포함하며, 4방향 탐색을 해줬습니다.

 

 

문제 접근 방법 - 3번

int mini = 2100000001;
    for (int i = 0; i <= K; i++) {
        if(check[H][W][i] != 0) mini = min(mini, check[H][W][i]);
    }
    if (mini != 2100000001) cout << mini - 1;
    else cout << "-1";
}

도착점서는 1부터 K까지 말처럼 이동하고 온 경우가 있습니다. 이들을 전부 비교해줍니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int K, W, H;
int check[201][201][31];
int monkey[201][201];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int horse_x[8] = { -2,-1,1,2,-2,-1,1,2 };
int horse_y[8] = { 1,2,2,1,-1,-2,-2,-1 };
typedef struct qu {
    int x;
    int y;
    int use_k;
}qu;


void bfs(int a, int b, int k) {
    queue<qu> q;
    q.push({ a,b,k });
    check[a][b][k] = 1;
    while (!q.empty()) {
        int x1 = q.front().x;
        int y1 = q.front().y;
        int k1 = q.front().use_k;
        q.pop();
        if (k1 < K) {
            for (int i = 0; i < 8; i++) {
                int xx = x1 + horse_x[i];
                int yy = y1 + horse_y[i];
                if (xx >= 1 && yy >= 1 && xx <= H && yy <= W) {
                    if (check[xx][yy][k1+1] == 0 && monkey[xx][yy] == 0) {
                        check[xx][yy][k1 + 1] = check[x1][y1][k1] + 1;
                        q.push({ xx, yy, k1 + 1 });
                    }
                }
            }
        }
        for (int i = 0; i < 4; i++) {
            int xx = x1 + dx[i];
            int yy = y1 + dy[i];
            if (xx >= 1 && yy >= 1 && xx <= H && yy <= W) {
                if (check[xx][yy][k1] == 0 && monkey[xx][yy] == 0) {
                    check[xx][yy][k1] = check[x1][y1][k1] + 1;
                    q.push({ xx, yy, k1 });
                }
            }
        }
    }
}

void solve() {
    bfs(1, 1, 0);
    int mini = 2100000001;
    for (int i = 0; i <= K; i++) {
        if(check[H][W][i] != 0) mini = min(mini, check[H][W][i]);
    }
    if (mini != 2100000001) cout << mini - 1;
    else cout << "-1";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> K;
    cin >> W >> H;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> monkey[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 댓글 남겨주세요!