말이 되고픈 원숭이 #1600 JAVA G3

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

1600번: 말이 되고픈 원숭이

BFS, DFS를 연습하기 좋은 문제를 풀었다.

처음에는 DFS로 접근을 했고 이후에 시간초과가 발생해서 BFS로 수정하였다.

 

 

아이디어로는 visited 3차원을 이용해야한다는 것이다. 각 움직임의 경우를 다르게 본다는 것이 문제해결의 핵심이었다.

처음에는 K번 이동을 어떻게 적절하게 해주지에 대한 고민이 있었는데 

BFS가 알아서 돌아줄것이라고 생각하고 안의 로직을 변경해줬다.

로직은 다음과같다. 

4방탐색 q에 저장 이후 K>0 이라면 (원숭이가 말처럼 뛸수 있다면) 말로 점프

 

DFS코드는 옳바르게 돌지만 시간초과이므로 주석처리 해 두었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	static int H,W,K;
	static int[][] map;
	static int ans = Integer.MAX_VALUE;
	static int[] dx= {1,-1,0,0}, dy= {0,0,1,-1};
	static int[] hx = {1,2,2,1,-1,-2,-2,-1};
	static int[] hy = {2,1,-1,-2,-2,-1,1,2};
	static boolean visited[][][] ;
	static class Monkey{
		int y,x,d,K;
		public Monkey(int y, int x, int d, int K) {
			this.y = y; 
			this.x = x;
			this.d =d;
			this.K = K;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		map = new int[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());
			}
		}
		visited = new boolean[H][W][K+1];
		visited[0][0][K] = true;
		//DFS(0,0,K,0);
		ans = BFS(0,0);
		if(ans ==Integer.MAX_VALUE) {
			System.out.println(-1);
			return;
		}
		System.out.println(ans);
		
		
	}
	
	
	private static int BFS(int sy, int sx) {
		ArrayDeque<Monkey> adq = new ArrayDeque<>();
		adq.offer(new Monkey(sy,sx,0,K));
		while(!adq.isEmpty()) {
			Monkey m = adq.poll();
			int cy = m.y;
			int cx = m.x;
			int cd = m.d;
			int k = m.K;
			if(cy == H-1 && cx == W-1) {
				return cd;
			}
			for(int i=0; i<4; i++) {
				int ny = cy + dy[i];
				int nx = cx + dx[i];
				if(check(ny,nx)) {
					if(map[ny][nx]==1)continue;
					if(!visited[ny][nx][k]) {
						visited[ny][nx][k] = true;
						adq.offer(new Monkey(ny,nx,cd+1,k));
					}
				}
			}
			if(k>0) {
				for(int i=0; i<8; i++) {
					int ny = cy + hy[i];
					int nx = cx + hx[i];
					if(check(ny,nx)) {
						if(map[ny][nx]==1)continue;
						if(!visited[ny][nx][k-1]) {
							visited[ny][nx][k-1]=true;
							adq.offer(new Monkey(ny,nx,cd+1,k-1));
						}
					}
				}
			}
			
			
		}
		return Integer.MAX_VALUE;
		
	}


	private static void DFS(int sy, int sx, int K, int dist) {
		
		//basis => 
		if(sy == H-1 && sx == W-1) {
			ans = Math.min(dist,ans);
			return;
		}
		
		//inductive -> 원숭이가 그냥 이동할때, 말처럼 이동할때
		for(int i=0; i<4; i++) {
			int ny = sy + dy[i];
			int nx = sx + dx[i];
			if(check(ny,nx)) {
				if(map[ny][nx]==1)continue;
				if(!visited[ny][nx][K]) {
					visited[ny][nx][K] = true;
					DFS(ny,nx,K,dist+1);
					visited[ny][nx][K] = false;
				}
			}
		}
		if(K>0) {
			for(int i=0; i<8; i++) {
				int ny = sy + hy[i];
				int nx = sx + hx[i];
				if(check(ny,nx)) {
					if(map[ny][nx]==1)continue;
					if(!visited[ny][nx][K-1]) {
						visited[ny][nx][K-1] = true;
						DFS(ny,nx,K-1,dist+1);
						visited[ny][nx][K-1] = false;
					}
				}
			}
		}
		
		
	}

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