[백준] 1600번 : 말이 되고픈 원숭이

문제

 

 

접근 방식

숨바꼭질 + 나이트의 이동 문제가 합쳐진 느낌의 문제인데

기존에는 가로세로, 가로세로상하 이렇게 이동했다면

이번에는 가로세로 + 나이트의 이동 방식 8가지가 합쳐진 BFS를 해야 한다.

 

총 12가지 방향으로 매번 탐색을 수행해 주면서 0,0에서 배열의 끝까지

갈 수 있는 최단 경로를 찾아주면 되는데

주의해야 할 점은 나이트의 이동 방식은 정해진 횟수만큼만 사용 가능하다.

 

예제 테스트케이스가 통과되는 코드를 작성하는 것은 쉬웠지만

막상 제출을 하니 계속해서 실패하였는데

처음에는 가로세로 이동과 나이트의 이동 모두

방문을 기록하는 배열을 공유해 봤고

두 번째에는 각각의 배열을 나눠서 사용해 봤는데

둘 다 공통적으로 발생하는 문제점이 있었다.

 

같은 배열을 쓰던 안 쓰던 나이트의 이동으로 앞서간 후에

가로세로를 탐색하여 방문 처리를 해버리면

이후에 오는 이동들이 모두 막혀버린다.

x 0 0 0
1 0 0 0
0 0 1 1
0 1 0 0

x m 0 0
1 0 h 0
0 h 1 1
0 1 0 0

x m h 0
1 h h h
h h 1 1
0 1 0 0

 

 

x가 시작지점 m이 원숭이가 가로세로로 이동하는 경로 h가 말처럼 이동하는 경로일 때

위와 같이 BFS로 탐색을 진행하는 과정을 살펴보면

말의 이동경로가 앞서 가서 모두 방문처리를 해버리기 때문에

원숭이가 가야 할 길이 모두 사라져 버린다.

 

그래서 이를 해결하기 위해 기존 방문 여부를 기록하던 2차원 배열을

3차원 배열로 바꾸어 말로 이동한 횟수로 분리하여 방문 여부를 기록했다.

 

즉, 말로 이동한 횟수가 같을 때만 방문 여부를 공유하고

다른 경우에는 방문 여부를 공유하지 않는다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int[] hx = {2, 2, 1, 1, -1, -1, -2, -2};
		int[] hy = {1, -1, 2, -2, 2, -2, 1, -1};

		int[] mx = {-1, 1, 0, 0};
		int[] my = {0, 0, -1, 1};

		int k = Integer.parseInt(br.readLine());

		st = new StringTokenizer(br.readLine());
		int w = Integer.parseInt(st.nextToken());
		int h = Integer.parseInt(st.nextToken());

		int[][] zoo = new int[h][w];
		boolean[][][] isVisited = new boolean[h][w][k + 1];

		int targetX = h - 1;
		int targetY = w - 1;

		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < w; j++) {
				zoo[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Queue<Monkey> monkeys = new LinkedList<>();
		monkeys.offer(new Monkey(0, 0, 0, 0));
		isVisited[0][0][0] = true;

		int min = -1;

		while (!monkeys.isEmpty()) {
			Monkey cur = monkeys.poll();

			int cx = cur.x;
			int cy = cur.y;
			int ch = cur.horse;
			int cm = cur.move;

			if (cx == targetX && cy == targetY) {
				min = cm;
				break;
			}

			if (ch < k) {
				for (int dir = 0; dir < 8; dir++) {
					int x = cx + hx[dir];
					int y = cy + hy[dir];

					if (x < 0 || x >= h || y < 0 || y >= w) continue;
					if (isVisited[x][y][ch + 1] || zoo[x][y] == 1) continue;

					isVisited[x][y][ch + 1] = true;
					monkeys.offer(new Monkey(x, y, ch + 1, cm + 1));
				}
			}

			for (int dir = 0; dir < 4; dir++) {
				int x = cx + mx[dir];
				int y = cy + my[dir];

				if (x < 0 || x >= h || y < 0 || y >= w) continue;
				if (isVisited[x][y][ch] || zoo[x][y] == 1) continue;

				isVisited[x][y][ch] = true;
				monkeys.offer(new Monkey(x, y, ch, cm + 1));
			}
		}

		System.out.println(min);
	}

	private static class Monkey {
		int x;
		int y;
		int horse;
		int move;

		public Monkey(int x, int y, int horse, int move) {
			this.x = x;
			this.y = y;
			this.horse = horse;
			this.move = move;
		}
	}
}