BOJ 1600 말이 되고픈 원숭이(JAVA) 🙊

문제 링크

1600번: 말이 되고픈 원숭이

문제 설명

(0, 0)에서 (H-1, W-1)까지의 최소 거리
단, 이동을 상하좌우 + K번만큼의 말의 이동

입력

K: 원숭이가 말의 이동방법으로 이동할 수 있는  횟수
W: 너비
H: 높이

출력

원숭이의 동작수의 최솟값, 시작점에서 도착점까지 갈 수 없는 경우엔 -1 출력

구조화

(0, 0)부터 bfs

말의 이동 방식으로 이동한 횟수가 K보다 작다면 말의 이동 방식으로 이동

방문체크 시에 이동한 횟수만큼의 배열을 만들어 각 경우의 수를 체크

최소 이동 경로이므로 bfs level 활용

 

sudo 코드

1. (0, 0)에서 bfs 시작

2. 사방탐색 후 cnt < K일 시에 말의 이동 방식으로 이동

3. (H-1, W-1)에 도착하면 bfs level return

소스 코드

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

public class Main {
	
	static class Node {
		
		int x;
		int y;
		int kCnt;
		
		public Node(int y, int x, int kCnt) {
			super();
			this.x = x;
			this.y = y;
			this.kCnt = kCnt;
		}

		@Override
		public String toString() {
			return "Node [x=" + x + ", y=" + y + ", kCnt=" + kCnt + "]";
		}
		
	}
	
	static int K, W, H;
	static int[][] map;
	static boolean[][][] visited;
	
	// 상 하 좌 우 + 말
	static int[][] way = {{-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 NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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];
		visited = new boolean[H][W][K+1];
		
		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());
			}
		}
		
		bfs();
	}
	
	private static void bfs() {
		
        int level = 0;
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(0,0,0));
		visited[0][0][0] = true;
		
		while(!q.isEmpty())
		{
			int size = q.size();
			while(size-- > 0)
			{
				Node cur = q.poll();
				int cx = cur.x;
				int cy = cur.y;
				int cCnt = cur.kCnt;
				
				// 도착지 체크
				if(cy==H-1 && cx==W-1)
				{
					System.out.println(level);
					return;
				}
				
				for(int w = 0; w < 4; w++)
				{
					int ny = cy + way[w][0];
					int nx = cx + way[w][1];
					// 경계 체크
					if(!isRight(ny, nx)) continue;
					// 장애물 체크
					if(map[ny][nx]==1) continue;
					// 방문 체크
					if(visited[ny][nx][cCnt]) continue;
					
					// 말의 이동 방법은 kCnt++
					q.add(new Node(ny, nx, cCnt));
					visited[ny][nx][cCnt] = true;
					
				}
				if(cCnt<K)
				{
					for (int w = 4; w < 12; w++) 
					{
						int ny = cy + way[w][0];
						int nx = cx + way[w][1];
						// 경계 체크
						if(!isRight(ny, nx)) continue;
						// 장애물 체크
						if(map[ny][nx]==1) continue;
						
						// 방문 체크
						if(visited[ny][nx][cCnt+1]) continue;
						
						q.add(new Node(ny, nx, cCnt+1));
						visited[ny][nx][cCnt+1] = true;
						
					}
				}
			}
			level++;
		}
		System.out.println(-1);
	}

	private static boolean isRight(int ny, int nx) {
		return (ny>=0&& ny<H && nx>=0 && nx<W);
	}

}