[백준 / Java] 1600번: 말이 되고픈 원숭이 (골드3)

문제 풀이 날짜: 2023.08.30
포스트 작성일: 2023.08.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1600번: 말이 되고픈 원숭이 (골드3)

 

키워드

BFS, 동적 계획법

 

풀이 접근법

• 말 처럼 움직이는 횟수는 총 K회로 제한된다. 그런데 먼저 K회를 모두 말 처럼 움직여버리면 다음의 케이스에서 더 이상 나아갈 수 없는 경우가 생긴다.

  2
  10 2
  0 0 1 0 0 1 0 0 1 0
  0 0 1 1 0 0 0 0 1 0

• 즉, 말처럼 움직인 경우와 원숭이가 그냥 이동한 경우를 구분하지 못하면 반례가 생긴다. 그렇기 때문에 각 탐색 때마다 말처럼 움직인 경우, 그냥 이동한 경우를 나누어 탐색한다.
• 즉, 말처럼 0-k번 움직인 경우의 수를 모두 별도의 배열로 관리한다. 마지막에는 이렇게 0부터 k번까지 말처럼 움직인 경우의 수 중에서 가장 최소인 값을 가져온다.
• DP 배열은 현재의 위치(r, c)와 말 처럼 움직인 횟수(k)의 정보를 동시에 가져야 하므로 3차원 배열로 선언한다.
• 메모리 초과가 쉽게 발생할 수 있으므로 위처럼 이미 구했던 점을 queue에 넣지 않도록 주의한다.
  • visited 배열 또한 DP 배열과 같은 원리로 선언하여, 원숭이가 k번째로 말처럼 움직였을 때의 DP값을 이미 구한 경우를 스킵시키는 용도로 사용한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

	private static int K;
	private static int W;
	private static int H;

	private static int[] hdr = { 2, 2, -2, -2, 1, -1, 1, -1 };
	private static int[] hdc = { 1, -1, 1, -1, 2, 2, -2, -2 };

	private static int[] mdr = { 0, 1, 0, -1 };
	private static int[] mdc = { 1, 0, -1, 0 };

	private static int[][] board;
	private static int[][][] DP;
	private static boolean[][][] visited;

	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(), " ");

		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());

		board = new int[H][W];
		DP = new int[H][W][K + 1]; //(r,c)에 다다를 때까지, K번만큼 말 처럼 움직인 결과를 기록
		visited = new boolean[H][W][K + 1];

		for (int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < W; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				
				for(int k = 0; k <= K; k++) {
					DP[i][j][k] = Integer.MAX_VALUE;
				}
			}
		}

		BFS(0, 0);

		int result = Integer.MAX_VALUE;
		for(int k = 0; k <= K; k++) { //k를 쓴 횟수마다 최소값을 따야 함
			result = Math.min(result, DP[H - 1][W - 1][k]);
		}
		
		if (W - 1 == 0 && H - 1 == 0) {
			result = 0;
		}
		else if (result == Integer.MAX_VALUE) {
			result = -1;
		}
		
		System.out.println(result);
	}

	private static void BFS(int startR, int startC) {
		Queue<Node> queue = new ArrayDeque<>();

		visited[startC][startR][0] = true;
		queue.add(new Node(startC, startR, 0));
		
		while (!queue.isEmpty()) {
			Node n = queue.poll();

			int nr = 0;
			int nc = 0;
			if (n.k < K) {
				// 1.말처럼 움직여보기 ==> K번만 움직일 수 있다.
				for (int i = 0; i < hdr.length; i++) {
					nr = n.row + hdr[i];
					nc = n.col + hdc[i];

					if (nr == 0 && nc == 0) {
						continue;
					}

					if (!isValid(nr, nc, n.k + 1)) { //k + 1번째 이동을 이미 처리했다면 continue
						continue;
					}

					// DP 갱신을 위해 방문체크 하지 않음
					if (DP[nr][nc][n.k + 1] >= DP[n.row][n.col][n.k] + 1) { // 이동횟수가 작거나 같다면
						DP[nr][nc][n.k + 1] = (DP[n.row][n.col][n.k] == Integer.MAX_VALUE) 
								? 1 : DP[n.row][n.col][n.k] + 1;
												
						if (nr == H - 1 && nc == W - 1) { return; }
						
						visited[nr][nc][n.k + 1] = true;
						queue.add(new Node(nr, nc, n.k + 1));
					}
				}
			}

			// 2.상하좌우만 이동 가능
			for (int i = 0; i < mdr.length; i++) {
				nr = n.row + mdr[i];
				nc = n.col + mdc[i];

				if (nr == 0 && nc == 0) {
					continue;
				}

				if (!isValid(nr, nc, n.k)) {
					continue;
				}

				// DP 갱신을 위해 방문체크 하지 않음
				if (DP[nr][nc][n.k] >= DP[n.row][n.col][n.k] + 1) { // 이동횟수가 작거나 같다면
					DP[nr][nc][n.k] = (DP[n.row][n.col][n.k] == Integer.MAX_VALUE) 
							? 1 : DP[n.row][n.col][n.k] + 1;
					
					if (nr == H - 1 && nc == W - 1) { return; }
					
					visited[nr][nc][n.k] = true;
					queue.add(new Node(nr, nc, n.k)); // count 변수 유지
				}
			}

		}

		return;
	}

	private static boolean isValid(int nr, int nc, int k) {
		return (nr > -1 && nc > -1 && nr < H && nc < W && !visited[nr][nc][k] && board[nr][nc] != 1);
	}
}

class Node {
	int row;
	int col;
	int k; // 말처럼 움직인 횟수

	public Node(int row, int col, int k) {
		this.row = row;
		this.col = col;
		this.k = k;
	}
}

---

 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/d7fc616fdbc06fdbf37eaa427959886d27734e52/%EB%B0%B1%EC%A4%80/Gold/1600.%E2%80%85%EB%A7%90%EC%9D%B4%E2%80%85%EB%90%98%EA%B3%A0%ED%94%88%E2%80%85%EC%9B%90%EC%88%AD%EC%9D%B4/%EB%A7%90%EC%9D%B4%E2%80%85%EB%90%98%EA%B3%A0%ED%94%88%E2%80%85%EC%9B%90%EC%88%AD%EC%9D%B4.java