[BJ] 1600. 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

✔ 첫번째 시도

1. v 배열을 3차원으로 사용한다. 세번째 인자가 0이면 말, 1이면 원숭이 방식으로 움직인 경우다.
2. 움직이기
   - 2-1) 지금까지 말 방식으로 움직인 경우가 K보다 작으면 (kCnt < K)
   • 1) 말 방식으로 움직인 후 (kCnt+1, 8방 탐색) → 큐에 넣고 방문 처리
   • 2) 원숭이 방식으로도 움직인 후 (kCnt, 4방 탐색) → 큐에 넣고 방문 처리

       - 2-2) 이미 K번 이상 말 방식으로 움직였다면 (kCnt ≥ K)
          - 1) 원숭이 방식으로만 움직인다. (kCnt, 4방 탐색) → 큐에 넣고 방문 처리

3. 도착지에 이르면 min값을 min(min, dist)로 갱신한다.

→ 결과는 fail..

 

🧨 문제는,,,,

1. 말 방식 → 원숭이방식 → 원숭이방식 ... 으로 도착지에 도달한 경우, 방문 체크가 모두 v[r][c][1]에 된다.
   • 이러면 원숭이방식→ 원숭이방식 → 원숭이방식 ...으로 도착지에 도달할 수 있을 경우, 이미 방문 체크가 되어있기 때문에 도착지까지 갈 수 없다!!
2. 좀 더 뒤에 발견한 문제점이지만..
   • 참고로 말은 장애물을 뛰어넘을 수 있다. → 이 말 뜻을, map[r][c]이 장애물이라도 이동할 수 있다는 의미인 줄 알았다. 그게 아니라 말이 이동하는 경유에 장애물이 있어도 상관 없다는 뜻이다.

👏 해결책은,,,,

• 3차원 v배열의 세번째 인자를, K+1만큼 선언한다. → K번 말 방식으로 뛰었을 때를 각각 체크한다.
• 이때 v[0][0][..]의 값들을 모두 true로 체크해주어야 시작 위치로 돌아가지 않는다.

 

✔ 두번째 시도

1. v 배열을 3차원으로 사용한다.
   map[r][c][K+1] 의 세번째 인자는, 말 방식으로 0, 1, ...., K번 뛰었을 때의 방문 체크를 위해서다.
2. 움직이기
   2-1). 지금까지 말 방식으로 움직인 경우가 K보다 작으면 (kCnt < K)
    - 1) 말 방식으로 움직인 후 (kCnt+1, 8방 탐색) → 큐에 넣고 방문 처리
    - 2) 원숭이 방식으로도 움직인 후 (kCnt, 4방 탐색) → 큐에 넣고 방문 처리
   2-2). 이미 K번 이상 말 방식으로 움직였다면 (kCnt ≥ K)
    - 1) 원숭이 방식으로만 움직인다. (kCnt, 4방 탐색) → 큐에 넣고 방문 처리
3. 도착지에 이르면 min값을 min(min, dist)로 갱신한다.

import java.io.*;
import java.util.*;
// 210324

public class Main_BJ_1600_말이되고픈원숭이 {
	static int K, W, H, min;
	static int[][] map;
	static int[] dr1 = {-1, -2, -2, -1, 1, 2, 2, 1}; // 말 방식
	static int[] dc1 = {-2, -1, 1, 2, -2, -1, 1, 2};
	static int[] dr2 = {0, -1, 0, 1}; // 원숭이 방식
	static int[] dc2 = {-1, 0, 1, 0};

	static class Pos {
		int r, c, kCnt, dist;

		public Pos(int r, int c, int kCnt, int dist) {
			this.r = r;
			this.c = c;
			this.kCnt = kCnt;
			this.dist = dist;
		}
		@Override
		public String toString() {
			return "Pos [r=" + r + ", c=" + c + ", kCnt=" + kCnt + ", dist=" + dist + "]";
		}
	}
	
	static void bfs() {
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[H][W][K+1]; 
		
		// 시작 위치
		q.offer(new Pos(0, 0, 0, 0)); 
		Arrays.fill(v[0][0], true);
		
		Pos cur;
		int nr, nc;
		
		while(!q.isEmpty()) {
			cur = q.poll();
			if(cur.r == (H-1) && cur.c == (W-1)) {
				// min 갱신				
				System.out.println(cur);
				min = Math.min(min, cur.dist);
				continue;
			}
			
			// 말 움직임
			if(cur.kCnt < K) { // 말로 움직인 횟수가 아직 남아있음
				for(int d=0; d<8; d++) {
					nr = cur.r + dr1[d];
					nc = cur.c + dc1[d];
					if(nr<0 || nr>=H || nc<0 || nc>=W || v[nr][nc][cur.kCnt+1]) continue;
					if(map[nr][nc]==1) continue; 
					q.offer(new Pos(nr, nc, cur.kCnt+1, cur.dist+1));
					v[nr][nc][cur.kCnt+1] = true;
				}
			}
			
			// 원숭이 
			for(int d=0; d<4; d++) {
				nr = cur.r + dr2[d];
				nc = cur.c + dc2[d];
				if(nr<0 || nr>=H || nc<0 || nc>=W || v[nr][nc][cur.kCnt]) continue;
				if(map[nr][nc]==1) continue; 
				q.offer(new Pos(nr, nc, cur.kCnt, cur.dist+1));
				v[nr][nc][cur.kCnt] = true;
			}
			
		} // while
		
	}
	
	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/input_BJ_1600_말이되고픈원숭이.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		K = stoi(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		W = stoi(st.nextToken());
		H = stoi(st.nextToken());
		min = Integer.MAX_VALUE;
		
		map = new int[H][W];
		for(int r=0; r<H; r++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int c=0; c<W; c++) {
				map[r][c] = stoi(st.nextToken());
			}
		}
		
		bfs();
		System.out.println((min==Integer.MAX_VALUE ? -1 : min));
		br.close();
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}

}