[BOJ] 1600 말이 되고픈 원숭이 (Java)

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

알고리즘

BFS

참고

금융 IT님 티스토리

풀이

모든 좌표에서 원숭이의 이동횟수를 완전탐색한다.
최단 거리를 구해야하므로 BFS를 적용한다.
말처럼 이동한 횟수를 고려해야하므로 3차원 visited 배열을 이용한다.

코드

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

public class Main {

	static int K, COUNT, W, H, pan[][];
	static boolean[][][] v;

	static int[] jumpy = {-1, -2, -2, -1, 1, 2, 2, 1};
	static int[] jumpx = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int[] dy = {1, -1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static Queue<Monkey> q;
	
	static class Monkey{
		int y;
		int x;
		int cnt;
		int k;
		public Monkey(int y, int x, int cnt, int k) {
			super();
			this.y = y;
			this.x = x;
			this.cnt = cnt;
			this.k = k;
		}
	}
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		K = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		pan = new int[H][W];
		v = new boolean[K+1][H][W];
		for(int i=0; i<H; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<W; j++) {
				pan[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		q = new ArrayDeque<>();
		q.offer(new Monkey(0, 0, 0, 0));					// 0, 0 위치에 있는 원숭이를 큐에 넣고 시작 
		while(!q.isEmpty()) {
			Monkey monkey = q.poll();						// 원숭이를 큐에서 빼고 
			if(monkey.y==H-1 && monkey.x==W-1) {			// 원숭이가 pan의 마지막 좌표에 위차한다면 cnt값을 출력하고 종료 
				System.out.println(monkey.cnt);
				return;										 
			}
			
			for(int d=0; d<4; d++) {						// 상하좌우 4방탐색 시작 
				int ny = monkey.y+dy[d];					// 이동할 행 인덱스 
				int nx = monkey.x+dx[d];					// 이동할 열 인덱스 
				int cnt = monkey.cnt;						// 현재 원숭이가 이동한 횟수 
				int k = monkey.k;							// 현재 원숭이가 말처럼 이동한 횟수 
				if(ny<0||ny>=H || nx<0||nx>=W || pan[ny][nx]==1 || v[k][ny][nx]) continue;
															// 이동할 위치(ny, nx)가 pan의 범위 내이고, 이동할 수 있는 좌표이면서,
															// 말처럼 k번 이동했을 때, (ny,nx)가 방문되지 않았다면 진행 
				v[k][ny][nx] = true;						// 말처러 k번 이동했을 때의 pan의 (ny, nx)를 방문처리 
				q.offer(new Monkey(ny, nx, cnt+1, k));		// ny, nx, 이동횟수+1, 말처럼이동횟수로 초기화된 원숭이를 큐에 추가 
			}
			
			if(monkey.k == K) continue;						// 만약 K만큼 말처럼 이동했다면 아래 코드 진행 x
			
			for(int d=0; d<8; d++) {						// 말처럼 이동 8방탐색 
				int ny = monkey.y+jumpy[d];					// 말처럼 이동할 경우 다음 행 위치 
				int nx = monkey.x+jumpx[d];					// 말처럼 이동할 경우 다음 열 위치 
				int cnt = monkey.cnt;						// 원숭이가 이동한 횟수 
				int k = monkey.k + 1;						// 말처럼 이동했으므로, 이전 위치에서의 원숭이의 k값에 1을 더한값으로 초기화 
				if(ny<0||ny>=H || nx<0||nx>=W || pan[ny][nx]==1 || v[k][ny][nx]) continue;				
															// 이동할 위치(ny, nx)가 pan의 범위 내이고, 이동할 수 있는 좌표이면서,
															// 말처럼 k번 이동했을 때, (ny,nx)가 방문되지 않았다면 진행 
				v[k][ny][nx] = true;						// 방문처리 
				q.offer(new Monkey(ny, nx, cnt+1, k));		// 원숭이 좌표 업데이트 
			}
		}
		
		System.out.println(-1);
		br.close();
	}

}