[백준] 1600 말이 되고픈 원숭이 / 자바(Java)

문제

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

1600번: 말이 되고픈 원숭이

 

---

해설

원숭이가 2차원 판을 시작지점에서 도착지점까지 이동하는 최소 횟수를 구하는 문제입니다.

 

최소횟수를 얻으며 각 계산이 독립적이므로 완전탐색이 필요하므로 해결방법으로 BFS가 떠오릅니다.

여기서 K번만 가능한 체스의 나이트처럼 뛰는 횟수가 문제가 됩니다. 특정 위치의 방문 여부가 K가 남아있는가에 따라 다음 이동 가능 여부가 달라지기 때문에 이를 해결하기 위해서 dp배열을 3차원으로 만들어 줍니다.

 

dp[i][j][k] : (i,j) 위치에서 점프(나이트처럼움직임)이 k개 남은 경우

 

일반적인 BFS처럼 꾸미되 큐에 넘겨주는 정보에 K를 포함시킵니다.

각 BFS의 진행별로 만약 K가 남아있다면 나이트처럼 이동하는 8방 탐색을 추가로 실시하며 없다면 인접한 구역을 이동하는 4방탐색을 진행합니다.

반복 중에 최종 값에 도착한다면 BFS이기 때문에 해당 값이 최소값이 보장되므로 바로 return해줍니다.

주의점

• 남은 K의 수의 관리
• 4방, 8방탐색 실수하지 않기

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	static class point {
		int r,c;
		int cnt, k;
		public point(int r, int c, int cnt, int k) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.k = k;
		}


		
	}

	static int dr[] = {-1,0,1,0};
	static int dc[] = {0,1,0,-1};
	static int hr[] = {-2,-1,1,2,2,1,-1,-2};
	static int hc[] = {1,2,2,1,-1,-2,-2,-1};
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int K = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int C = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		
		int map[][] = new int [R][C];
		for(int i=0;i<R;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<C;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// dp배열에 인접이동으로 가는데 걸리는 비용과 남은 K수
		int dp[][][] = new int [R][C][K+1];

		
		
		int ans = bfs(map, dp, new point(0, 0, 0, K));
		System.out.println(ans);
	}
	
	static int bfs(int map[][], int dp[][][], point input) {
		Queue<point> q = new LinkedList<>();
		q.add(input);
		boolean find=false;
		int ans=0;
		dp[0][0][input.k]=0; 
		while(!q.isEmpty()) {
			int size = q.size();
			for(int i=0;i<size;i++) {
				point current = q.poll();
				if(current.r==map.length-1 && current.c==map[0].length-1) {
					find=true;
					ans = current.cnt;
					break;
				}
				//k가 남은 경우 말처럼 이동
				if(current.k>0) {
					for(int idx=0;idx<8;idx++) {
						int newr = current.r + hr[idx];
						int newc = current.c + hc[idx];
						
						if(newr<0 || newc<0 || newr>=map.length || newc >=map[0].length) continue;
						
						if(map[newr][newc]==1) continue;
						
						if(dp[newr][newc][current.k-1]==0) {
							dp[newr][newc][current.k-1]=current.cnt+1;						
							q.add(new point(newr, newc, current.cnt+1, current.k-1));
						}
					}
				}
				
				// 일반 인접 이동
				for(int idx=0;idx<4;idx++) {
					int newr = current.r + dr[idx];
					int newc = current.c + dc[idx];
					
					if(newr<0 || newc<0 || newr>=map.length || newc >=map[0].length) continue;
					
					if(map[newr][newc]==1) continue;
					
					if(dp[newr][newc][current.k]==0) {
						dp[newr][newc][current.k]=current.cnt+1;						
						q.add(new point(newr, newc, current.cnt+1, current.k));
					}
				}
			}
			if(find) break;
		}
		
		if(find) return ans;
		else return -1;
	}
}