[백준/boj] 1600: 말이 되고픈 원숭이 (Java) / BFS / 3차원 배열

문제

1600번: 말이 되고픈 원숭이

전체 코드

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map;
	static boolean[][][] visited;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dxH = { -2, -1, -2, -1, 1, 2, 2, 1 };
	static int[] dyH = { -1, -2, 1, 2, -2, -1, 1, 2 };
	static int N, M, K;

	static private class Pos {
		int x;
		int y;
		int k; // 말처럼 이동할 수 있는 횟수
		int move; // 이동 횟수

		public Pos(int x, int y, int k, int move) {
			this.x = x;
			this.y = y;
			this.k = k;
			this.move = move;
		}
	}

	public static void main(String[] args) throws Exception {
		K = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		visited = new boolean[N][M][K + 1];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		if (map[0][0] == 1 || map[N - 1][M - 1] == 1) {
			System.out.println(-1);
			return;
		}
		int answer = bfs();
		answer = answer == Integer.MAX_VALUE ? -1 : answer;
		System.out.println(answer);
	}

	private static int bfs() {
		Deque<Pos> deque = new ArrayDeque<Pos>();
		deque.add(new Pos(0, 0, 0, 0));
		int nx, ny;
		int minNum = Integer.MAX_VALUE;
		while (!deque.isEmpty()) {
			Pos pos = deque.poll();
			int x = pos.x;
			int y = pos.y;
			int k = pos.k;
			int move = pos.move;
			if (x == N - 1 && y == M - 1) {
				minNum = Math.min(minNum, move);
				continue;
			}
			move++;
			for (int i = 0; i < 4; i++) {
				nx = x + dx[i];
				ny = y + dy[i];
				if (!isRange(nx, ny) || map[nx][ny] == 1 || visited[nx][ny][k])
					continue;
				deque.add(new Pos(nx, ny, k, move));
				visited[nx][ny][k] = true;
			}

			if (k < K) {
				for (int i = 0; i < 8; i++) {
					nx = x + dxH[i];
					ny = y + dyH[i];
					if (!isRange(nx, ny) || map[nx][ny] == 1 || visited[nx][ny][k + 1])
						continue;
					deque.add(new Pos(nx, ny, k + 1, move));
					visited[nx][ny][k+1] = true;
				}
			}
		}
		return minNum;
	}

	private static boolean isRange(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= M ? false : true;
	}
}

설명

• N : 세로 길이(H) / M : 가로 길이(W) / K : 말처럼 이동할 수 있는 횟수
• visited[x][y][k] : 말처럼 k번 이동한 경우에 (x,y) 좌표에 방문했었는지 여부
• dx , dy : 인접한 방향으로 이동
• dxH, dyH : 말처럼 이동

Pos

• x: x좌표
• y: y좌표
• k: 말처럼 이동한 횟수 (K보다 작거나 같음)
• move: (x,y) 좌표까지 오기위해 이동한 횟수

함수 bfs()

• minNum : (N-1, M-1) 좌표로 도달한 모든 경우 중 가장 적은 이동 횟수를 담는 변수 (함수가 끝나고 Integer.MAX_VALUE 가 할당되어 있다는 것은 도달하지 못했다는 것을 의미)
• k : 현재 위치에 도달하기까지 말처럼 이동한 횟수
• move: 현재 위치에 도달하기까지 이동한 횟수( 말 + 인접 )

인접한 곳만 이동하는 경우

move++;
for (int i = 0; i < 4; i++) {
	nx = x + dx[i];
    ny = y + dy[i];
	if (!isRange(nx, ny) || map[nx][ny] == 1 || visited[nx][ny][k])
		continue;
	deque.add(new Pos(nx, ny, k, move));
	visited[nx][ny][k] = true;
}

이동할 위치가 1. 범위가 벗어나거나, 2. 장애물이 있거나, 3. 말처럼 이동한 횟수가 같은 상태에서 이동할 위치에 들린적 있다면 continue

그렇지 않다면 new Pos(이동할 위치 x좌표, 이동할 위치 y좌표, 말처럼 이동하지 않은 경우이므로 그대로 k, 한번 증가한 이동횟수)를 deque에 add한다.

말처럼 이동하는 경우

if (k < K) {
for (int i = 0; i < 8; i++) {
	nx = x + dxH[i];
	ny = y + dyH[i];
	if (!isRange(nx, ny) || map[nx][ny] == 1 || visited[nx][ny][k + 1])
		continue;
	deque.add(new Pos(nx, ny, k + 1, move)); // 위에서 move++ 해서 move는 1 증가되어 있다.
	visited[nx][ny][k+1] = true;
	}
}

말처럼 이동할 수 있는 횟수가 남아있는 경우 (k < K) 에만 실행된다.

이동할 위치가 1. 범위가 벗어나거나, 2. 장애물이 있거나, 3. 말처럼 이동한 횟수가 같은 상태에서 이동할 위치에 들린적 있다면 continue

그렇지 않다면 new Pos(이동할 위치 x좌표, 이동할 위치 y좌표, 말처럼 이동한 경우이므로 k+1 , 한번 증가한 이동횟수)를 deque에 add한다.

마지막 좌표에 도달!

if (x == N - 1 && y == M - 1) {
	minNum = Math.min(minNum, move);
	continue;
}

말처럼 이동한 횟수와 시점에 따라서 여러번 도달할 것이다. 이 중 가장 적은 이동 횟수를 minNum에 담는다.

이동할 필요가 없으므로 continue 해준다.

minNum이 답이된다 !  (Integer.MAX_VALUE 인 경우엔 -1 이 답!)