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

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

1600번: 말이 되고픈 원숭이

1. 유형

DP, BFS

 

2. 로직

1. bfs를 돌리면서 조건에 맞는 경우만 큐에 넣어주기

시뮬레이션을 돌리면 위 같은 상황이 나온다.

현재 좌표에서는 이전에 말처럼 이동했는지 알수 없다.

따라서 dp[말처럼 이동 횟수][행][열]인 3차원 배열에 이동거리를 저장하고, 

저장한 것 보다 더 작은 이동회수가 있을겨우만 큐에 삽입하면 된다.

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
	static int K, N, M, map[][], dp[][][], answer;
	static int[][] d = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 },
			{ 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 } };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		K = stoi(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		M = stoi(st.nextToken());
		N = stoi(st.nextToken());
		init();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		bfs();
		if(answer == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(answer);
	}

	static void bfs() {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { 0, 0, K, 0 });
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			if (cur[0] == N - 1 && cur[1] == M - 1) {
				answer = Math.min(answer, cur[3]);
				continue; 
			}
			for (int k = 0; k < 12; k++) {
				int nr = cur[0] + d[k][0];
				int nc = cur[1] + d[k][1];
				if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == 1)
					continue;
				if (k > 3 && cur[2] > 0 && dp[cur[2]-1][nr][nc] > cur[3] + 1) {
					dp[cur[2] - 1][nr][nc] = cur[3] + 1;
					q.add(new int[] { nr, nc, cur[2] - 1, cur[3] + 1 });
				} else if (k < 4 && dp[cur[2]][nr][nc] > cur[3] + 1) {
					dp[cur[2]][nr][nc] = cur[3] + 1;
					q.add(new int[] { nr, nc, cur[2], cur[3] + 1 });
				}
			}
		}
	}

	static int stoi(String token) {
		return Integer.valueOf(token);
	}

	static void init() {
		answer = Integer.MAX_VALUE;
		map = new int[N][M];
		dp = new int[K+1][N][M];
		for (int k = 0; k < K+1; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (i == 0 && j == 0)
						continue;
					dp[k][i][j] = Integer.MAX_VALUE;
				}
			}
		}
	}
}