BOJ - 1600 ) 말이 되고픈 원숭이

 

---

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

1600번: 말이 되고픈 원숭이

---

원숭이는 K번 말처럼 움직일 수 있다. 왼쪽 끝 ( 0,0 ) 에서 시작하여 ( y-1 , x-1 )까지 이동하면서 

최단경로를 구하는 문제이다.

 

최단경로를 구하기위해 BFS알고리즘을 사용했으나.. 방문처리가 상당히 까다로웠다.

 

먼저, 말처럼이동할 수 있는 횟수가 정해져 있기 때문에, 목적지에 말처럼이동해야지만 갈수있는경우, 

방문체크를 이차원으로 한다면, 답을 구하지 못 할 수 있다. 

 

3차원으로 늘려 말의 경우로 이동한경우와 원숭의의 경우로 이동한경우로 두가지로 나눈다면,

말->원숭이->말->원숭이 이러한 경로에서 답이 구해지지 않음에도 방문처리가 되는 경우로 예외가

발생한다.

 

즉 K만큼의 이차원배열을 방문체크의 배열로 사용하는것이 이문제의 핵심이다.

경로가 곂치는 것은 알았지만, K 개까지 확장해서 생각하는 반례를 찾는데 40분이나 걸렸다.ㅠ

---

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


public class 말이되고픈원숭이 {
	public static class node{
		int y,x;
		int canMove;
		int cnt;
		public node(int y, int x, int canMove, int cnt ) {
			this.y = y;
			this.x = x;
			this.canMove = canMove;
			this.cnt = cnt;
			
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int k = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int x  =Integer.parseInt(st.nextToken());
		int y  =Integer.parseInt(st.nextToken());
		int map[][] = new int[y][x];
		boolean visit[][][] = new boolean [k+1][y][x];
		
		for(int i = 0 ; i < y; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < x ; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		visit[k][0][0] = true;
		
		
		ArrayDeque<node> dq = new ArrayDeque<>();
		dq.add(new node(0, 0, k, 0 ));
		int answer = -1;
		// 원숭이의 이동 
		int dir_monkey[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		// 말의 이동
		int dir_horse[][] = {{1,2},{2,1},{-1,2},{2,-1},{1,-2},{-2,1},{-1,-2},{-2,-1}};
		while(!dq.isEmpty()) {
			node now = dq.poll();
			int r = now.y;
			int c = now.x;
			int can = now.canMove;
			
			if(r== y-1 && c == x-1) {
				answer = now.cnt;
				break;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int ny  = r + dir_monkey[i][0];
				int nx  = c + dir_monkey[i][1];
				if(ny >= 0 && nx>= 0 && ny < y && nx < x ) {
					if(map[ny][nx] ==0 && !visit[can][ny][nx]) {
						visit[can][ny][nx] = true;
						dq.add(new node(ny,nx,can,now.cnt+1 ));
					}
				}
			}
			
			if(can >0) {
				for(int i = 0 ; i < 8 ; i++) {
					int ny  = r + dir_horse[i][0];
					int nx  = c + dir_horse[i][1];
					if(ny >= 0 && nx>= 0 && ny < y && nx < x ) {
						if(map[ny][nx] ==0 && !visit[can-1][ny][nx]) {
							visit[can-1][ny][nx] = true;
							dq.add(new node(ny,nx,can-1,now.cnt+1));
						}
					}
				}
			}
		}
		System.out.print(answer);
	}
}

---

뇌절..