[알고리즘] Java / 백준 / 말이 되고픈 원숭이 / 1600

[알고리즘] Java / 백준 / 말이 되고픈 원숭이 / 1600

문제

문제 링크

접근 방식

3차원 visited배열을 사용하여 말 이동 가능 횟수까지의 방문을 처리하고 bfs로 목표지점까지 탐색한다

코드

import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;

public class Main_1600_정현명 {

	static int K,W,H;
	static boolean[][] map;
	static boolean visited[][][];
	static int[][] horseMove = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
	static int[][] monkeyMove = {{-1,0},{0,1},{1,0},{0,-1}};
	static int mvCnt = Integer.MAX_VALUE;
	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());
		
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		map = new boolean[H][W];
		
		for(int r=0;r<H;r++) {
			st = new StringTokenizer(br.readLine());
			for(int c=0;c<W;c++) {
				if(Integer.parseInt(st.nextToken())==1) map[r][c] = true;
			}
		}
		
		bfs();

	}
	
	public static void bfs() {
		
		
		visited = new boolean[H][W][K+1];
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {0,0,0,0});
		
		visited[0][0][0] = true;
		
		while(!queue.isEmpty()){
			int[] info = queue.poll();
			int r= info[0];
			int c= info[1];
			int k= info[2];
			int moveCnt = info[3];
			
			if(r == H-1 && c == W-1) {
				System.out.println(moveCnt);
				return;
			}
			
			
			
			// 원숭이 동작으로 이동하기
			for(int i=0;i<4;i++) {
				int nextR = r + monkeyMove[i][0];
				int nextC = c + monkeyMove[i][1];
				
				if(nextR < 0 || nextR >= H || nextC < 0 || nextC >= W || visited[nextR][nextC][k] || map[nextR][nextC]) continue;
				visited[nextR][nextC][k] = true;
				queue.add(new int[] {nextR,nextC,k,moveCnt+1});
			}
			
			// 말 동작으로 이동하기
			if(++k<=K) {
				for(int i=0;i<8;i++) {
					int nextR = r + horseMove[i][0];
					int nextC = c + horseMove[i][1];
					
					if(nextR < 0 || nextR >= H || nextC < 0 || nextC >= W || visited[nextR][nextC][k] || map[nextR][nextC]) continue;
					visited[nextR][nextC][k] = true;
					queue.add(new int[] {nextR,nextC,k,moveCnt+1});
				}
			}
		}
		System.out.println(-1);
		return;
		
		
	}

}