[Java] BOJ1600_말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

---

Knight처럼 이동하거나 상, 하, 좌, 우 네 방향을 이동해서 도착점까지 이동해야 한다. 이때 Knight처럼 이동하는 것은 K번만 가능하다.

 

BFS로 탐색하는 문제에서 Knight로 이동하는 조건이 추가된 문제이다. 이런 경우 Knight이동을 1번만 한 경우, 2번 한 경우,... K번 한 경우를 다 고려해서 최소 동작 수를 구해줘야 한다. 따라서 방문 처리 배열을 index와 knight 이동 횟수를 담는 3차원 배열로 선언해주었다.

 

bfs를 돌 때 Queue에 현재위치, 이동 횟수, knight 이동 횟수를 담아주었다.

상, 하, 좌, 우 사방으로 이동할 때는 이동횟수만 증가시킨 채 Queue에 담고 Knight로 이동할 때는 knight 이동 횟수 또한 증가시켜서 Queue에 담아주었다. 이때 Knight 이동 횟수가 K번 이하인지 확인해야 한다.

 

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

public class Main {

	static int K, R, C;
	static int[][] arr;
	static boolean[][][] visit;
	static int[] dr = { -1, 0, 1, 0, -2, -1, 1, 2, 2, 1, -1, -2};
	static int[] dc = { 0, -1, 0, 1, -1, -2, -2, -1, 1, 2, 2, 1};
	static int res = -1;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		arr = new int[R][C];
		visit = new boolean[R][C][K+1];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		bfs(0, 0);
		System.out.println(res);
	}
	private static void bfs(int r, int c) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {r, c, 0, 0});  //r, c, 거리, knight
		visit[r][c][0] = true;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			if (temp[0] == R - 1 && temp[1] == C - 1) {
				res = temp[2];
				break;
			}
			
			for (int i = 0; i < 12; i++) {
				int nr = temp[0] + dr[i];
				int nc = temp[1] + dc[i];
				
				if(nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
				if(i <= 3 && arr[nr][nc] == 0 && !visit[nr][nc][temp[3]]) { //사방으로 한칸 이동하는 경우
					q.offer(new int[] {nr, nc, temp[2]+1, temp[3]});
					visit[nr][nc][temp[3]] = true;
				} else if(i >= 4 && temp[3] < K && arr[nr][nc] == 0 && !visit[nr][nc][temp[3]+1]) { //knight처럼 이동하는 경우 
					q.offer(new int[] {nr, nc, temp[2]+1, temp[3]+1});
					visit[nr][nc][temp[3]+1] = true;
				}
			}
		}
	}

}