boj 1600 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

bfs 탐색인데 4방탐색에 위 사진과 같은 이동방식이 추가되었습니다.

위 사진처럼 말과 같이 움직일 수 있는 횟수가 K로 정해져있습니다. (0 <= K <= 30)

 

그러므로 방문체크는 3차원 배열로 해줍니다.

visit[x][y][k] : 말과 같이 움직인 횟수가 k번인 상태로 (x, y)에 도착한 경우

 

저는 방향탐색에 대한 좌표이동을 인덱스를 기준으로 나누었습니다.

1. 0 ~ 3번 인덱스 : 4방탐색

2. 4 ~ 11번 인덱스 : 말처럼 이동

4방탐색의 경우 k의 변화 없이 이동시켜줍니다.

말처럼 이동하는 경우 K미만으로 움직였을 경우에만 움직여줍니다.

 

(N - 1, M - 1)에 도달하였으면 시간을 출력합니다.

 

 

[C++]

#include <iostream>
#include <queue>
using namespace std;
 
queue<pair<pair<int, int>, pair<int, int> > > q;
bool visit[200][200][31];
int map[200][200];
int x_direct[] = { 0,1,0,-1,-2,-1,1,2,2,1,-1,-2 }, y_direct[] = { 1,0,-1,0,1,2,2,1,-1,-2,-2,-1 };
int K, H, W, ans = -1;
 
void bfs() {
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int cnt = q.front().second.first;
        int horse = q.front().second.second;
        q.pop();
 
        if (x == H - 1 && y == W - 1) {
            ans = cnt;
            return;
        }
 
        for (int i = 0; i < 12; i++) {
            int xx = x + x_direct[i];
            int yy = y + y_direct[i];
 
            if (xx < 0 || yy < 0 || xx >= H || yy >= W) continue;
            if (map[xx][yy] == 1) continue;
 
            if (x_direct[i] == 2 || x_direct[i] == -2 || y_direct[i] == 2 || y_direct[i] == -2) {
                if (visit[xx][yy][horse + 1] || horse == K) continue;
                q.push(make_pair(make_pair(xx, yy), make_pair(cnt + 1, horse + 1)));
                visit[xx][yy][horse + 1] = true;
            }
            else {
                if (visit[xx][yy][horse]) continue;
                q.push(make_pair(make_pair(xx, yy), make_pair(cnt + 1, horse)));
                visit[xx][yy][horse] = true;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> K >> W >> H;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> map[i][j];
        }
    }
 
    q.push(make_pair(make_pair(0, 0), make_pair(0, 0)));
    visit[0][0][0] = true;
    bfs();
 
    cout << ans << '\n';
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[201][201];
    static boolean visit[][][] = new boolean[201][201][31];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 },
            { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } };
    static int N, M, K;
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.add(new int[] { 0, 0, 0 });
        visit[0][0][0] = true;
        for (int t = 1;; t++) {
            int size = dq.size();
            while (size-- > 0) {
                int x = dq.peek()[0];
                int y = dq.peek()[1];
                int cnt = dq.poll()[2];
 
                if (x == N - 1 && y == M - 1) {
                    System.out.println(t - 1);
                    return;
                }
 
                for (int i = 0; i < 12; i++) {
                    int nx = x + direct[i][0];
                    int ny = y + direct[i][1];
 
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    if (list[nx][ny] == 1)
                        continue;
 
                    if (i < 4) {
                        if (visit[nx][ny][cnt])
                            continue;
                        dq.add(new int[] { nx, ny, cnt });
                        visit[nx][ny][cnt] = true;
                    } else {
                        if (cnt + 1 > K || visit[nx][ny][cnt + 1])
                            continue;
                        dq.add(new int[] { nx, ny, cnt + 1 });
                        visit[nx][ny][cnt + 1] = true;
                    }
                }
            }
 
            if (dq.isEmpty()) {
                System.out.println(-1);
                return;
            }
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}