백준 1600번 : 말이 되고픈 원숭이

 문제

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

1600 말이 되고픈 원숭ㅇ

 

 구현 방법

 최소한의 동작을 구해야 하기 때문에 bfs를 사용하여 풀어주었습니다.

보통의 bfs/dfs 문제와 다르게 k번만 따로 동작을 할 수 있습니다.

평소에 방문처리를 R, C 로만 했다면 이 문제는 말 움직임을 관리하는 K까지 처리를 해줘야하므로 3차원 배열을 사용해주어야 합니다.

 

bfs를 돌려 원숭이의 움직임으로 움직이고 만약 현재 원숭이가 말의 움직임을 할 수 있다면 말의 움직임도 구해줍니다. 

 

 구현 코드

package BOJ.Gold;

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

public class BOJ1600_말이되고픈원숭이 {
	static int R, C, K;
	static int[][] map;
	static int[][] deltaM = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 원숭이 이동
	static int[][] deltaH = { { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 }, { -2, -1 } }; // 말이동
	static boolean[][][] visited;
	static Queue<Monkey> queue;
	static class Monkey {
		int r, c, horse;

		public Monkey(int r, int c, int horse) {
			super();
			this.r = r;
			this.c = c;
			this.horse = horse;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		K = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[R][C];
		for (int r=0;r<R;r++) {
			st = new StringTokenizer(br.readLine());	
			for (int c=0;c<C;c++) {
				map[r][c] = Integer.parseInt(st.nextToken());
			}
		}
		queue = new LinkedList<>();
		visited = new boolean[R][C][K+1];
		queue.offer(new Monkey(0, 0, 0));
		visited[0][0][0] = true;
		System.out.println(bfs());
	}
	
	static int bfs() {
		int cnt = 0;
		while(!queue.isEmpty()) {
			int size = queue.size();
			for (int i=0;i<size;i++) {
				Monkey now = queue.poll();
				if(now.r == R-1 && now.c == C-1) return cnt; // 도착하면 끝
				
				move(deltaM, now, true); // 원숭이 이동
				if(now.horse < K) move(deltaH, now, false); // 현재 말 움직임을 할 수 있다면
			}
			cnt++;
		}
		return -1;
	}
	
	static void move(int[][] deltas, Monkey now, boolean isMonkey) {
		for (int d = 0; d < deltas.length; d++) {
			int nr = now.r + deltas[d][0];
			int nc = now.c + deltas[d][1];

			if (isIn(nr, nc) && map[nr][nc] == 0) {
				int horseMove = isMonkey ? now.horse : now.horse + 1; // 말의 움직임이라면 말 움직임 키워주기
				if (!visited[nr][nc][horseMove]) {
					Monkey newMonkey = new Monkey(nr, nc, horseMove);
					queue.add(newMonkey);
					visited[nr][nc][horseMove] = true; // 방문처리
				}
			}
		}
	}

	static boolean isIn(int r, int c) {
		return 0 <= r && r < R && 0 <= c && c < C;
	}
}

 

정답!