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

1.  문제 링크

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

2.  문제

요약

• 동물원에서 막 탈출한 원숭이 한 마리는 말이 되기를 간절히 원해 말의 움직임을 살펴보고 그대로 따라 하기로 하였습니다.
• 말은 격자판에서 체스의 나이트와 같은 이동방식을 가집니다. 이동 시에 말은 장애물을 뛰어넘을 수 있습니다.
• 말은 체스의 나이트와 같이 움직일 수 있지만 원숭이는 K번만 체스의 나이트와 같이 움직일 수 있고 그 외에는 대각선 방향을 제외한 인접한 칸으로 움직일 수 있습니다.
• 원숭이는 격자판 맨 왼쪽 위에서 시작하여 맨 오른쪽 아래까지 가야 합니다.
• 인접한 네 방향으로 한 번 움직이는 것, 체스의 나이트처럼 한 번 움직이는 것 모두 한 번의 동작으로 칩니다.
• 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 문제입니다.
• 입력: 첫 번째 줄에 0보다 크거나 같고 30보다 작거나 같은 정수인 K가 주어지고 두 번째 줄에는 1보다 크거나 같고 200보다 작거나 같은 자연수인 격자판의 가로 길이 W와 세로 길이 H가 주어집니다. 세 번째 줄부터 H개의 줄에는 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻합니다.
  • 장애물이 있는 곳으로는 이동할 수 없습니다.
  • 시작점과 도착점은 항상 평지입니다.
• 출력: 첫 번째 줄에 원숭이의 동작수의 최솟값을 출력합니다. 시작점에서 도착점까지 갈 수 없는 경우에는 -1을 출력합니다.

3.  소스코드

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

public class Main {
	static int K, H, W;
	static int[][] map;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static int[] hdx = {-2, -1, 1, 2, 2, 1, -1, -2}, hdy = {1, 2, 2, 1, -1, -2, -2, -1};
	static void input() {
		Reader scanner = new Reader();
		K = scanner.nextInt();
		W = scanner.nextInt();
		H = scanner.nextInt();
		map = new int[H][W];
		for(int row = 0; row < H; row++) {
			for(int col = 0; col < W; col++) map[row][col] = scanner.nextInt();
		}
	}
	
	static void solution() {
		int result = bfs();
		System.out.println(result);
	}
	
	static int bfs() {
		Queue<Monkey> queue = new LinkedList<>();
		queue.offer(new Monkey(0, 0, 0, K));
		boolean[][][] visited = new boolean[H][W][K + 1];
		visited[0][0][K] = true;
		int min = -1;
		while(!queue.isEmpty()) {
			Monkey cur = queue.poll();
			if(cur.x == (H - 1) && cur.y == (W - 1)) {
				min = cur.move;
				break;
			}
			for(int dir = 0; dir < 4; dir++) {
				int cx = cur.x + dx[dir], cy = cur.y + dy[dir];
				if(isInMap(cx, cy)) {
					if(!visited[cx][cy][cur.horseMove] && map[cx][cy] == 0) {
						visited[cx][cy][cur.horseMove] = true;
						queue.offer(new Monkey(cx, cy, cur.move + 1, cur.horseMove));
					}
				}
			}
			if(cur.horseMove > 0) {
				for(int dir = 0; dir < 8; dir++) {
					int cx = cur.x + hdx[dir], cy = cur.y + hdy[dir];
					if(isInMap(cx, cy)) {
						if(!visited[cx][cy][cur.horseMove - 1] && map[cx][cy] == 0) {
							visited[cx][cy][cur.horseMove - 1] = true;
							queue.offer(new Monkey(cx, cy, cur.move + 1, cur.horseMove - 1));
						}
					}
				}
			}
		}
		return min;
	}
	
	static boolean isInMap(int x, int y) {
		if(x >= 0 && x < H && y >= 0 && y < W) return true;
		return false;
	}
	
	static class Monkey {
		int x, y, move, horseMove;
		public Monkey(int x, int y, int move, int horseMove) {
			this.x = x;
			this.y = y;
			this.move = move;
			this.horseMove = horseMove;
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• Monkey라는 클래스를 생성합니다.
  • 해당 클래스는 현재 원숭이가 위치한 곳의 x, y좌표 값, 원숭이가 움직인 횟수, 원숭이가 체스의 나이트와 같이 움직일 수 있는 횟수를 멤버 변수로 갖습니다.
• BFS를 통해 시작 지점부터 도착 지점까지 탐색을 진행하는데, 각 위치의 방문 여부를 3차원 배열 visited로 체크합니다.
  • visited[x][y][k] = 체스의 나이트와 같이 움직일 수 있는 횟수가 k번 남았을 때 (x, y) 위치를 방문했는지 여부
• 시작 위치인 (0, 0)에서 체스의 나이트와 같이 움직일 수 있는 횟수가 K번 남았을 때 0번 움직인 원숭이를 Queue에 넣고 BFS 탐색을 시작합니다. 이 때, visited[0][0][K]에 대해서는 방문 체크를 실시합니다.
• Queue가 빌 때까지 Queue에서 Monkey 객체를 하나씩 꺼내서 해당 객체가 이동할 수 있는 곳을 체크한 후에 이동할 수 있는 곳을 Queue에 넣습니다.
  • 만약 Queue에서 꺼낸 객체의 위치가 도착 위치라면 그 때의 이동 횟수를 반환합니다.
  • Queue에서 꺼낸 객체의 위치에서 상하좌우 위치를 확인하여 해당 위치가 현재 말처럼 이동할 수 있는 횟수에서 방문되지 않았고 장애물이 존재하지 않는다면 이동 횟수를 1 늘린 채로 해당 위치를 Monkey 객체에 담아 Queue에 넣어 다음 탐색 시에 활용합니다.
  • 만약 아직 말처럼 이동할 수 있는 횟수가 남았다면 말이 이동할 수 있는 8개의 위치에 대해 똑같이 확인하고 가능하다면 이동 횟수는 1 늘리고 말처럼 이동할 수 있는 횟수는 1 줄여서 해당 위치를 Monkey 객체에 담아 Queue에 넣어 다음 탐색 시에 활용합니다.
• BFS 탐색을 모두 마친 후에 도착 위치로 갈 수 없다면 -1을, 가능하다면 최소 이동 횟수를 출력합니다.