백준 1600 : 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

[ 문제풀이 ]

일반적인 bfs + dp 문제에서 말로 움직일 수 있는 방법만 추가된 문제이다.

3차원 배열을 하나 선언해서 말의 방향으로 움직인 횟수에 따라 방문 표시를 해주면 된다.

가로길이가 W이고 세로길이가 H인 것만 주의하자.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int y, x, k, move;
		
		public Node(int y, int x, int k, int move) {
			this.y = y;
			this.x = x;
			this.k = k;
			this.move = move;
		}
	}
	
	static int K, W, H;
	static int[][] map;
	static int[][][] visit;
	
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	static int[][] horse = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1},{1,2}};
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			K = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			map = new int[H][W];
			visit = new int[K + 1][H][W];
			for (int i = 0; i < H; ++i) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < W; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
					for (int k = 0; k <= K; ++k) {
						visit[k][i][j] = (int)1e9;
					}
				}
			}
			bw.write(bfs() + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static int bfs() {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0, 0, 0, 0));
		visit[0][0][0] = 0;
		while (!q.isEmpty()) {
			Node n = q.poll();
			
			if (n.y == H - 1 && n.x == W - 1) {
				return n.move;
			}
			
			//일반적인 4방향 탐색
			for (int d = 0; d < 4; ++d) {
				int ny = n.y + dir[d][0];
				int nx = n.x + dir[d][1];
				
				if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
				if (map[ny][nx] == 1) continue;
				if (visit[n.k][ny][nx] != (int)1e9 && visit[n.k][ny][nx] <= n.move + 1) continue;
				visit[n.k][ny][nx] = n.move + 1;
				q.offer(new Node(ny, nx, n.k, n.move + 1));
			}
			
			if (n.k >= K) continue;
			//말이 갈 수 있는 8방향 탐색
			for (int d = 0; d < 8; ++d) {
				int ny = n.y + horse[d][0];
				int nx = n.x + horse[d][1];

				if (ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
				if (map[ny][nx] == 1) continue;
				if (visit[n.k + 1][ny][nx] != (int)1e9 && visit[n.k + 1][ny][nx] <= n.move + 1) continue;
				visit[n.k + 1][ny][nx] = n.move + 1;
				q.offer(new Node(ny, nx, n.k + 1, n.move + 1));
			}
		}
		return -1;
	}
}