/ BOJ

BOJ_1600_말이되고픈원숭이_JAVA

문제 : 말이되고픈원숭이

링크 : BOJ_1600_말이되고픈원숭이

접근 방식

이전에 풀었던 벽 부수고 이동하기와 비슷한 맥락의 문제인 것 같다. 벽 부수고 이동하기에서는 벽을 부쉈을 때와 부수지 않았을 때의 차원을 나누어 구분해야 했기 때문에 3차원 배열을 사용했다. 이 문제도 같은 방식으로 접근하여 풀 수 있었다.

최소 이동 횟수를 구해야 하기 때문에 BFS를 사용했다. 또한 기본의 4방향이동에 더해 추가로 나이트의이동 문제에서 적용했던 체스판의 나이트 이동도 단위 벡터 이동에 추가하여 총 12개의 이동방식을 저장해두었다.

이제 BFS로 왼쪽 위부터 시작하여 오른쪽 아래로 이동하는 길을 탐색하는데, 벽 부수고 이동하기 처럼 나이트 처럼 이동하는 순간 차원을 바꾸어 점프한 횟수 별로 맵을 옮겨 저장해야 하는 방식으로 탐색을 진행했다. 이 작업은 주어진 점프 기회의 횟수보다 현재 점프한 횟수가 작을 경우에만 작동하도록 해야 자원 낭비를 막을 수 있다.

소스 코드

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

public class BOJ_1600_말이되고픈원숭이 {
	static int K, N, M, arr[][];
	static int[][] dir = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { -2, -1 }, { -1, -2 }, { -2, 1 }, { -1, 2 },
			{ 2, -1 }, { 1, -2 }, { 2, 1 }, { 1, 2 } };

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		K = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());

		arr = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		bfs(new Node2(0, 0, 0, 0), new boolean[N][M][K + 1]);

	}

	public static void bfs(Node2 node, boolean[][][] visited) {

		Queue<Node2> queue = new LinkedList<>();
		queue.offer(node);
		visited[node.x][node.y][0] = true;

		while (!queue.isEmpty()) {
			Node2 temp = queue.poll();

			if (temp.x == N - 1 && temp.y == M - 1 && temp.jump <= K) {
				System.out.println(temp.dep);
				return;
			}

			for (int d = 0; d < 12; d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];

				if (dx >= 0 && dx < N && dy >= 0 && dy < M) {

					if (arr[dx][dy] == 0) {

						if (d <= 3 && visited[dx][dy][temp.jump] == false) {

							visited[dx][dy][temp.jump] = true;
							queue.offer(new Node2(dx, dy, temp.jump, temp.dep + 1));

						} else if (d > 3 && temp.jump < K && visited[dx][dy][temp.jump + 1] == false) {

							visited[dx][dy][temp.jump + 1] = true;
							queue.offer(new Node2(dx, dy, temp.jump + 1, temp.dep + 1));

						}
					}
				}
			}
		}

		System.out.println(-1);
		return;

	}

}

class Node2 {

	int x;
	int y;
	int jump;
	int dep;

	public Node2(int x, int y, int jump, int dep) {
		this.x = x;
		this.y = y;
		this.jump = jump;
		this.dep = dep;
	}
}

풀이 방법

  1. line 9 ~ 11 : 멤버 변수 선언부

  2. line 15 ~ 31 : 멤버 변수에 값 할당(input)

  3. line 33 : bfs 호출

  4. line 37 ~ 78 : bfs 메서드 내부 매개변수로 Node 객체, 방문정보를 체크할 3차원 배열을 받는다.

  5. line 46 ~ 49 : 목적지에 도착하면 현재 노드의 깊이를 출력하고 리턴(종료조건)

  6. line 51 ~ 72 : 반복하여 4방탐색 + 나이트점프 탐색을 진행한다. d가 0,1,2,3일경우에는 일반적인 사방탐색이므로 현재 점프상태의 방문 배열에 방문처리를 해야한다. d가 4보다 큰 경우에는 나이트의 이동, 즉 점프를 하게 되는 것이므로 3차원의 점프 횟수에 대한 값을 1 증가시킨 후 방문처리를 해야한다.

  7. line 75 : 목적지에 도달하지 못했을 때 -1을 출력하고 리턴

  8. line 82 ~ 95 : BFS 탐색을 할 때 사용할 좌표값을 가지고 있는 객체를 생성할 클래스. 멤버변수로 좌표값, 현재 점프한 횟수, 깊이 값23 가지고 있다.