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

1. 문제 링크

1600번: 말이 되고픈 원숭이

 

2. 문제 및 입출력예제

 

3. 문제 풀이

bfs로 탐색하는 문제이다.

K번까지 움직일 수 있다고 정해져있기 때문에 좌표에 도착했을 때 몇번째로 도착했는지까지 생각해서 visit을 3차원 배열로 했다.

말의 움직임을 따랐을 때 움직임의 횟수를 증가하고, 원숭이의 움직임인 4방탐색의 경우에는 움직임의 횟수를 그대로 둔 상태로 이동한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Point{
		int x;
		int y;
		int k;
		public Point(int x, int y, int k) {
			super();
			this.x = x;
			this.y = y;
			this.k = k;
		}
	}
	static int[] horseX = {-2, -1, 1, 2, 2, 1, -1, -2};
	static int[] horseY = {1, 2, 2, 1, -1, -2, -2, -1};
	static int[] monkeyX = {1, -1, 0, 0};
	static int[] monkeyY = {0, 0, 1, -1};
	static int K, N, M, result;
	static boolean[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		String[] split = br.readLine().split(" ");
		M = Integer.parseInt(split[0]);
		N = Integer.parseInt(split[1]);
		map = new boolean[N][M];
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				if(split[j].equals("0")) {
					map[i][j] = true;
				}
				else {
					map[i][j] = false;
				}
			}
		}
		result = 0;
		bfs();
		System.out.println(result);
	}
	private static void bfs() {
		Queue<Point> queue = new ArrayDeque<>();
		boolean[][][] visit = new boolean[N][M][K+1];
		queue.offer(new Point(0, 0, 0));
		visit[0][0][0] = true;
		Point now = null;
		int count=0, X=0, Y=0;
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int i=0;i<size;i++) {
				now = queue.poll();
				if(now.x == N-1 && now.y==M-1) {
					result = count;
					return;
				}
				for(int hd=0;hd<8;hd++) {
					X = now.x+horseX[hd];
					Y = now.y+horseY[hd];
					if(X<0 || X>=N || Y<0 || Y>=M || now.k+1>K || !map[X][Y] || visit[X][Y][now.k+1]) {
						continue;
					}
					queue.offer(new Point(X, Y, now.k+1));
					visit[X][Y][now.k+1] = true;
				}
				for(int md=0;md<4;md++) {
					X = now.x+monkeyX[md];
					Y = now.y+monkeyY[md];
					if(X<0 || X>=N || Y<0 || Y>=M || !map[X][Y] || visit[X][Y][now.k]) {
						continue;
					}
					queue.offer(new Point(X, Y, now.k));
					visit[X][Y][now.k] = true;
				}
			}
			count++;
		}
		result = -1;
	}	
}