BOJ. 1600번. 말이 되고픈 원숭이

 

 

말이 되고픈 원숭이... 나를 보는 것 같다^^.
이 문제는 일반적인 BFS를 하되,  1. 평범하게 상하좌우로 움직일 수 도 있고  / 2. 말로 움직일 수 도 있다.
따라서 방문체크를 할 때, 당시의 말의 움직인 횟수가 영향을 미치기 때문에 차원을 3차원으로 늘려서 케이스를 나눠 생각해야 한다. 이 아이디어만 생각해낸다면 쉬운 BFS문제이다.

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

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 BOJ1600 {

	static int k,w,h;
	static int ans=Integer.MAX_VALUE;
	static int[][] map;
	static boolean[][][] c;
	
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	static int[] hy = {-2,-1, 1, 2, 2, 1,-1,-2};
	static int[] hx = { 1, 2, 2, 1,-1,-2,-2,-1};
	
	static class Pos{
		int y,x,m,km;
		public Pos(int y, int x, int m,int km) {
			this.y = y;
			this.x = x;
			this.m = m;
			this.km = km;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		k = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		
		map = new int[h][w];
		c = 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());
			}
		}
		
		solution();
		
		System.out.println(ans==Integer.MAX_VALUE ? -1 : ans);
	}

	private static void solution() {
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(new Pos(0,0,0,0));
		c[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			
			if(cur.y == h-1 && cur.x == w-1) {
				ans = Math.min(ans, cur.m);
			}
			
			for(int d=0; d<4; d++) {
				int ny = cur.y+dy[d];
				int nx = cur.x+dx[d];
				int nk = cur.km;
				if(checkBound(ny,nx) && !c[ny][nx][nk] && map[ny][nx]!=1) {
					q.add(new Pos(ny,nx,cur.m+1,nk));
					c[ny][nx][nk] = true;
				}
			}
			
			if(cur.km<k) {
				for(int h=0; h<8; h++) {
					int ny = cur.y+hy[h];
					int nx = cur.x+hx[h];
					int nk = cur.km + 1;
					if(checkBound(ny,nx) && !c[ny][nx][nk] && map[ny][nx]!=1) {
						q.add(new Pos(ny,nx,cur.m+1,nk));
						c[ny][nx][nk] = true;
					}
				}
			}
			
		}
	}
	
	private static boolean checkBound(int y, int x) {
		return (y>=0 && y<h && x>=0 && x<w) ? true : false;
	}
	
}