BOJ_1600_ 말이 되고픈 원숭이

1. 

구분: 그래프 이론, 그래프 탐색, 너비 우선 탐색 

언어: Java
전략: 
원숭이가 스킬을 쓴 횟수 만다 다른 상태를 가진다. --> 다른 상태 배열을 만들어야 한다. 

가장 최소로 이동하고 싶으니 우선적으로 말처럼 이동하는 것을 다 쓰도록 한다. 

말 스킬을 다 쓰면 이제 한 칸씩 이동한다. 

---

2. 코드

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

public class Main {
	
	static class Node{
		//x,y 좌표와 이동 횟수를 나타내는 level, 말처럼 뛴 횟수를 나타내는 breakn 
		int x, y, level, breakn;
		Node(int y, int x, int level, int breakn){
			this.y = y;
			this.x = x;
			this.level = level; 
			this.breakn = breakn;
		}
	}
	
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int k = scanner.nextInt();
		int w = scanner.nextInt();
		int h = scanner.nextInt();
		
		
		//원숭이가 뛴 횟수에 따라 다른 방문확인 배열을 가져야 한다. 
		//즉 i번 말처럼 하먼 그 다음부터는 [][][i]배열을 이용
		boolean[][][] visited = new boolean[h][w][k+1];
		int[][] map = new int[h][w];
		for(int i = 0; i<h; i++) {
			for(int j = 0; j<w; j++) {
				map[i][j] = scanner.nextInt();
			}
		}
		//한 칸씩 이동
		int[] dx = {1,-1,0,0};
		int[] dy = {0,0,1,-1};
		//말처럼 이동
		int[] hx = {1,2,2,1,-1,-2,-2,-1};
		int[] hy = {-2,-1,1,2,2,1,-1,-2};
		
		int ans = -1; //정답
		
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0,0,0,0));
		
		visited[0][0][0] = true;
		
		while(!q.isEmpty()) {
			Node n = q.poll();
			int qx = n.x;
			int qy = n.y;
			int qlevel = n.level;
			int qbreakn = n.breakn;
			
			
			if(qx==w-1 && qy==h-1) {
				//원하는 위치에 도닳한다면 그만
				ans = qlevel;
				break;
			}
			
			if(qbreakn<k) {
				//말 처럼 뛸 수 있다  - 계속 말처럼 뛰자
				for(int hh= 0; hh<8; hh++) {
					int hhx = qx + hx[hh];
					int hhy = qy + hy[hh];
					//한번 뛴것이다 
					//범위 체크
					if(hhx<0 || hhy <0 || hhx>=w || hhy>=h )
						continue;
					//장애물이면 지나가 
					if(map[hhy][hhx]==1) continue;
					//이미 방문했었다면 지나가 
					if(visited[hhy][hhx][qbreakn+1]) continue;
					
					//이제 한번 뛰었으니까 이제부터는 +1한 배열로
					visited[hhy][hhx][qbreakn+1] = true;
					//층과 뛴 횟수 1씩 증가해서 큐에 넣어
					q.offer(new Node(hhy, hhx, qlevel+1, qbreakn+1));
					
				}
			}
	

			for(int d = 0; d<4; d++) {
				int nx = qx + dx[d];
				int ny = qy + dy[d];
				//이때는 말 스킬 쓴경우가 아니다 
				
				//범위 체크
				if(nx<0 || ny <0 || nx>=w || ny>=h)
					continue;
				//장애물과 방문여부 체크
				if(map[ny][nx]==1 || visited[ny][nx][qbreakn])continue;
				
				
				visited[ny][nx][qbreakn] = true;
				q.offer(new Node(ny, nx, qlevel+1, qbreakn));
	
			}
		}//while
		
		System.out.println(ans);
		
	}

}

---

3

어렵다. 원숭이도 싫고 말도 싫다

초기 level을 1로 설정해서 답이 계속 잘못 나왔다. - 시작점은 늘 0이라는 사실을 잊지 말자!

그래프 탐색과 탐색을 동시에 살펴야 하는 문제이다. 잘 익히면 좋을 것 같다.