[백준] 1600 말이 되고픈 원숭이 (Java)

[1600 말이 되고픈 원숭이]

난이도: 골드4

1600번: 말이 되고픈 원숭이

문제

입력

출력

---

[아이디어]

문제 자체는 BFS를 활용하면 된다는 것이 바로 보인다. 하지만, 일반 BFS를 활용했다가는 틀렸습니다를 만나게 될 것이다. 이 문제는 말의 이동 횟수에 따라 방문 여부를 다르게 관리해줘야 한다는 것이 문제의 핵심이다.

 

visited 배열을 3차원으로 만든다. visited[i][j][k] 에서 i는 행, j는 열, k는 말처럼 움직인 횟수를 나타낸다.

여기서 k는 0~K 의 값을 가져야하는데, 말처럼 움직인 횟수가 0번부터 K번까지 가능하기 때문이다.

 

BFS로 탐색할 때, 일반 원숭이처럼 움직이는 경우와 말처럼 움직이는 경우 모두를 고려해줘야한다. 이 때, 현재 말처럼 이동한 횟수가 K번보다 작아야지 말처럼 이동이 가능하다.

 

마지막으로 먼저 목적지에 도착한다고해서 움직인 횟수가 최소가 되지 않으므로 도착했다고 반복문을 빠져나가면 안된다!

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Point {
		int r, c, cnt, horse; // horse: 말 처럼 움직인 횟수
		
		public Point(int r, int c, int cnt, int horse) {
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.horse = horse;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens;
		
		int K = Integer.parseInt(br.readLine());
		tokens = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(tokens.nextToken());
		int N = Integer.parseInt(tokens.nextToken());
		
		int [][] map = new int[N][M];
		for(int r = 0; r < N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 0; c < M; c++) {
				if(tokens.nextToken().charAt(0) == '1') map[r][c] = 1; // 장애물을 -1로 표현
			}
		}
		
		int [] hdr = {-2, -1, 1, 2, 2, 1, -1, -2}, hdc = {1, 2, 2, 1, -1, -2, -2, -1}; // 말 이동
		int [] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; // 일반 이동
		
		boolean [][][] visited = new boolean[N][M][K + 1]; // 말 이동 횟수에 따라 방문 여부 판단 <- 포인트
		Queue<Point> Q = new LinkedList<>();
		Q.offer(new Point(0, 0, 0, 0));
		visited[0][0][0] = true;
		
		int result = Integer.MAX_VALUE;
		while(!Q.isEmpty()) {
			Point now = Q.poll();
			
			if(now.r == N - 1 && now.c == M - 1) { // 도착!
				result = Math.min(result, now.cnt);
				// break; // 이거 있으면 최소를 못구함!!!
			}

			// 기본 이동
			for(int i = 0; i < 4; i++) {
				int nr = now.r + dr[i];
				int nc = now.c + dc[i];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 범위 벗어남
				if(now.horse > K || visited[nr][nc][now.horse] || map[nr][nc] == 1) continue; // 벽 또는 이미 지남
				
				Q.offer(new Point(nr, nc, now.cnt + 1, now.horse));
				visited[nr][nc][now.horse] = true;
			}

			// 말처럼 이동
			if(now.horse < K) {
				for(int i = 0; i < 8; i++) {
					int nr = now.r + hdr[i];
					int nc = now.c + hdc[i];
					
					if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 범위 벗어남
					if(visited[nr][nc][now.horse + 1] || map[nr][nc] == 1) continue; // 벽 또는 이미 지남
					
					Q.offer(new Point(nr, nc, now.cnt + 1, now.horse + 1));
					visited[nr][nc][now.horse + 1] = true;
				}
			}
		}
		
		if(result == Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

}