[백준-1600] 말이 되고픈 원숭이

이 문제는 백준 골드5 레벨의 문제이다. 

 

 

이 문제는 벽 부수고 이동하기랑 비슷한 문제이다. 벽 부수고 이동하기보다 조금 더 어려운 것 같은데, 레벨은 더 낮다. 왜지... 근데 벽 부수고 이동하기 문제 풀기 전에 이 문제를 만났다면 못 풀었을 것 같다.

 

이 문제의 포인트는 평상시처럼 4방향만 도는게 아니라 말처럼 움직이는 것 까지, 총 12 방향으로 움직이는 것을 고려해 주어야 한다는 것이다. 델타 배열을 사용해서 움직일건데 인덱스가 0부터 3일때 까지는 왼쪽부터 시계방향으로, 4-11까지는 대각선으로 움직이게 만들었다.

 

bfs를 돌 떄,

1) 칸을 넘어가거나, 방문 할 수 없는 곳이라면 pass.

2) 말 처럼 움직일 건데 점프 횟수가 남아있지 않아도 pass.

3) 벽 부수고 이동하기 때 처럼 같은 상태로 방문 한 적 있으면 pass.

4) 한 칸씩 이동하는 걸로 방문할 수 있다면 방문해보기 

5) 점프 할 수 있다면 점프해보기

 

이렇게 돌면서 목적지에 도달하면 걸린 횟수를 출력해 주었다. 

처음에는 문제를 푸는데 테스트 케이스나 질문에 올라온 반례들은 다 맞는데 메모리 초과가 나길래 왜 그런가 고민해보니, 3번 방문 처리를 잘못해주어서 그랬다. 한 칸씩 움직이는 경우와 점프를 하는 경우를 따로 생각해 주었어야 했는데 그냥 같이 처리해 주었더니 오류가 난 것이었다. 따로 생각해 주었더니 통과 됐다. 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 말숭이_1600 {
	static int K; //말처럼 움직일 수 있는 수
	static int W,H; //맵 크기
	static int[][] map;
	static boolean[][][] visited; //방문여부 + 점프 체크
	static int ans = Integer.MAX_VALUE;
	
	static int[] dr = {0,-1,0,1,-1,1,2,2,-1,1,-2,-2}; //좌,상,우,하
	static int[] dc = {-1,0,1,0,-2,-2,-1,1,2,2,1,-1}; //대각선까지
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		K = sc.nextInt();
		W = sc.nextInt();
		H = sc.nextInt();
		
		map = new int[H][W];
		visited = new boolean[H][W][K+1];
		
		for(int i=0; i<H; i++) { //맵 받아주기
			for(int j=0; j<W; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		bfs();
		
		if(ans == Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(ans);
	}
	
	static void bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0,0,0,0));
		visited[0][0][0] = true;
		
		
		while(!q.isEmpty()) {
			Point p = q.poll();
		
			//도착했으면 끝!
			if(p.x == H-1 && p.y == W-1) {
				ans = p.cnt;
				break;
			}
			
			for(int i=0; i<12; i++) {
				int nr = p.x + dr[i];
				int nc = p.y + dc[i];
				
				//칸 넘어가면 pass
				if(nr<0 || nc<0 || nr>=H || nc>=W)
					continue;
				//방문할 수 없다면 pass
				if(map[nr][nc] == 1)
					continue;
				//말처럼 움직이는데 점프 횟수가 남아있지 않다면 pass.
				if(i>=4 && p.jump >= K)
					continue;
				//한 칸씩 이동으로 방문 한 적 있으면 pass
				if(i<4 && visited[nr][nc][p.jump])
					continue;
				//말 처럼 뛰었을 때 방문 한 적 있으면 pass
				if(i>=4 && visited[nr][nc][p.jump+1])
					continue;
				
				//점프 안 하고 갈 수 있는 길은 가보기
				if(i<4){
					visited[nr][nc][p.jump] = true;
					q.add(new Point(nr,nc, p.cnt+1, p.jump));
				}
				//점프 할 수 있으면 점프 해보기.
				if(i>=4 && p.jump < K){					
					visited[nr][nc][p.jump+1] = true;
					q.add(new Point(nr,nc, p.cnt+1, p.jump+1));
				}
			}
		}
	}
	
	static class Point{
		int x,y, cnt, jump;
		Point(int x, int y, int cnt, int jump){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.jump = jump;
		}
	}

}