백준 1600번 <말이 되고픈 원숭이>

백준 알고리즘 1600번

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

1600번: 말이 되고픈 원숭이

---

1600번

동물원에서 막 탈출한 원숭이가 말이 되고 싶다.

말이 움직일 수 있는 경우는 아래와 같다. 참고로 말은 장애물을 뛰어넘을 수 있다.

그렇지만 원숭이는 능력이 부족해서 총 K번만 말과 같이 움직일 수 있고 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. (상, 하, 좌, 우)

원숭이가 격자판 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 최소한의 동작으로 갈 수 있는 방법을 알아내라.

 

입력으로 첫 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로 길이 W, 세로 길이 H가 주어진다.

그 다음 W 줄에 걸쳐 격자판의 상태가 주어지는데 0은 아무것도 없는 평지, 1은 장애물을 뜻한다.

 

출력으로 원숭이의 동작 수의 최솟값을 출력한다. 만약 맨 왼쪽 위에서 맨 오른쪽 아래까지 갈 수 없다면 -1을 출력한다.

---

문제 해결

최소 동작 수를 구하는 것이기 때문에 BFS를 사용하여 풀었다.

말처럼 움직이는 경우가 제한적이기 때문에 방문체크를 할 때, 해당 경우를 모두 고려해줘야 한다. 

그래서 방문 체크 배열이 3차원이다.

visit[ i ][ j ][ k ] = (i, j) 좌표를 k번 말처럼 움직여서 왔다는 의미이다.

 

(i, j) 칸에 오기 위해 필요한 말처럼 움직인 횟수(horse)와, 그냥 움직인 횟수(near)를 알기 위해 Tuple이라는 클래스를 만들어서 사용하였다. 총 이동 횟수는 horse와 near를 더한 값이다.

 

큐에서 Tuple을 꺼내면 아래의 프로세스를 진행한다.

1. Tuple의 값 중 horse의 값이 K보다 작다면 말처럼 움직인다.
2. 그냥 움직인다.

---

코드

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

public class Main {
	static class Tuple {
		int i, j, horse, near;

		public Tuple(int i, int j, int horse, int near) {
			super();
			this.i = i;
			this.j = j;
			this.horse = horse;
			this.near = near;
		}

	}

	static int[] di = { -1, 1, 0, 0 };
	static int[] dj = { 0, 0, -1, 1 };
	static int[] hi = { -2, -1, 1, 2, 2, 1, -1, -2 };
	static int[] hj = { 1, 2, 2, 1, -1, -2, -2, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		String[] inArr = br.readLine().split(" ");
		int C = Integer.parseInt(inArr[0]);
		int R = Integer.parseInt(inArr[1]);

		int[][] map = new int[R][C];
		boolean[][][] visit = new boolean[R][C][K + 1];
		for (int i = 0; i < R; i++) {
			inArr = br.readLine().split(" ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(inArr[j]);
			}
		}
		
		int ans = Integer.MAX_VALUE;
		if(R == 1 && C == 1) {
			ans = map[0][0]==0?0:-1;
			System.out.println(ans);
			System.exit(0);
		}
		
		Queue<Tuple> queue = new ArrayDeque<>();
		queue.add(new Tuple(0, 0, 0, 0));
		visit[0][0][0] = true;
		
		while (!queue.isEmpty()) {
			Tuple tp = queue.poll();
			if (tp.horse < K) {
				for (int k = 0; k < 8; k++) {
					int ni = tp.i + hi[k];
					int nj = tp.j + hj[k];
					if (ni < 0 || nj < 0 || ni >= R || nj >= C)
						continue;
					if (map[ni][nj] == 1)
						continue;
					if (visit[ni][nj][tp.horse + 1])
						continue;

					if (ni == R - 1 && nj == C - 1) {
						ans = Math.min(ans, tp.horse + 1 + tp.near);
						continue;
					}
					visit[ni][nj][tp.horse + 1] = true;
					queue.add(new Tuple(ni, nj, tp.horse + 1, tp.near));

				}
			}

			for (int k = 0; k < 4; k++) {
				int ni = tp.i + di[k];
				int nj = tp.j + dj[k];
				if (ni < 0 || nj < 0 || ni >= R || nj >= C)
					continue;
				if (map[ni][nj] == 1)
					continue;
				if (visit[ni][nj][tp.horse])
					continue;
				if (ni == R - 1 && nj == C - 1) {
					ans = Math.min(ans, tp.horse + 1 + tp.near);
					continue;
				}

				visit[ni][nj][tp.horse] = true;
				queue.add(new Tuple(ni, nj, tp.horse, tp.near + 1));
			}
		}
		ans = ans == Integer.MAX_VALUE ? -1 : ans;
		System.out.println(ans);
	}

}

---

결과

---