백준 알고리즘 - 1600 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

  백준 알고리즘의 1600번 문제 말이 되고픈 원숭이입니다.

 

어제 포스팅 했던 '벽 부수고 이동하기1'과 비슷한 문제입니다.

 

comlib.tistory.com/17

백준 알고리즘 2206 - 벽 부수고 이동하기1

 

  이번 문제가 어제 문제와 다른 점은 visited의 관리 횟수가 어제는 0, 1, 2라면 오늘은 K개로 더 많이 정해준다는 점입니다. 그걸 제어하기 위해 오늘도 visited를 int의 2차원 배열로 만든 다음에 관리합니다.

 

 

  아무도 방문하지 않은 값을 0이 아닌 -1로 초기화시키고 해당 칸에 visited 체크를 할 때에는 방문한 element가 가지고 있는 남은 말 움직임 횟수를 적어줍니다. 이후 다른 element가 해당 칸을 왔을 때 만일 이미 적혀있는 visited의 말 움직임 횟수보다 새로 온 element의 말 움직임 횟수가 크다면 이전에 적혀있던 visited 방문 체크를 무시하고 다시 방문하게 됩니다.

  이런식으로 동작한다면 가능한 모든 경우를 체크할 수 있습니다.

 

 

  여담으로 이 문제는 다른 문제와 다르게 가로 - 세로 순으로 input을 주기 때문에 평소 세로 - 가로에 익숙하신 분들은 값을 반대로 받아야 합니다. 저는 이것때문에 근 1시간 날렸네요. 다들 조심하세요!

 

 

  아래는 제 코드입니다.

 

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

public class Main_BJ_1600_말이되고픈원숭이_bfs {

	private static int K, W, H;
	private static int[][] input;
	private static int[][] visited;
							// 상, 하, 좌, 우
	private static int[] dy = {0, 0, -1, 1};
	private static int[] dx = {-1, 1, 0, 0};
						// 왼쪽 위부터 시계방향
	private static int[] hy = {-2, -1, 1, 2, 2, 1, -1, -2};
	private static int[] hx = {-1, -2, -2, -1, 1, 2, 2, 1};
	
	private static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		K = Integer.parseInt(br.readLine());

		StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
		
		// 가끔 이런 문제같이 세로 - 가로 순으로 주지 않고 가로 - 세로 순으로 주는 경우가 있다.
		// 이 경우 x가 H가 아닌 W로 들어가버리니 반대로 입력을 받아야 한다!
		H = Integer.parseInt(tk.nextToken());
		W = Integer.parseInt(tk.nextToken());
		
		input = new int[W][H];
		
		// -1 : 미방문, 0 : 말 움직임이 불가능한 경우가 방문, n : 말 움직임의 가능 여부에 따라 입력
		visited = new int[W][H];
		
		for(int i = 0; i < W; i++) {
			for(int j = 0; j < H; j++) {
				visited[i][j] = -1;
			}
		}
		
		for(int i = 0; i < W; i++) {
			tk = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < H; j++) {
				input[i][j] = Integer.parseInt(tk.nextToken());
			}
		}
		
		bfs();
		
		if(min == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(min);
	}

	private static void bfs() {
		Queue<int[]> que = new ArrayDeque<int[]>();
		
		//					(0, 0), K번 말 움직임, count 0;
		que.offer(new int[] {0, 0, K, 0});
		visited[0][0] = K;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			int x = cur[0];
			int y = cur[1];
			int horseMove = cur[2];
			int count = cur[3];
			
			if(x == W-1 && y == H-1) {
				min = count;
				return;
			}
			
			for(int i = 0; i < 4; i++) {
				int ty = y + dy[i];
				int tx = x + dx[i];
				
				if(tx >= 0 && ty >= 0 && tx < W && ty < H) {
					if(input[tx][ty] == 0 && visited[tx][ty] < horseMove) {
						// 지나간 지점에는 visited 표기
						visited[tx][ty] = horseMove;
						que.offer(new int[] {tx, ty, horseMove, count+1});
					}
				}
			}
			
			// 말 움직임 탐색
			if(horseMove > 0) {
				for(int i = 0; i < 8; i++) {
					int ty = y + hy[i];
					int tx = x + hx[i];
					
					// 1회 소모 후 visited 검사.
					if(tx >= 0 && ty >= 0 && tx < W && ty < H) {
						if(input[tx][ty] == 0 && visited[tx][ty] < horseMove-1) {
							visited[tx][ty] = horseMove-1;
							que.offer(new int[] {tx, ty, horseMove-1, count+1});
						}
					}
				}			
			}
		}
	}
}