2020 - 블록 이동하기

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

[ 문제풀이 ]

2020 카카오 블라인드 기출 마지막 문제이다. 18. 19. 20년도 기출을 풀어보면서 느끼는 거지만 문제 배치가 난이도 순인 것은 아닌 것 같다.

​전형적인 bfs + dp 문제이다. 현재 로봇의 위치에서 상하좌우로 이동 및 회전할 수 있는 경우의 수를 bfs(최소 거리)를 통해 탐색해주면서 dp를 활용해 중복 방문을 해결하면 쉽게 해결할 수 있다.

​로봇의 상태는 2가지이기 때문에 이를 구분하기 위해 state라는 변수를 사용하였다.

다음으로 각 상태마다 가능한 모든 상태를 탐색해주면 된다. 가능한 상태는 총 8가지이다.

이때 중복 방문을 방지하기 위해 dp를 다음과 같이 정의하였다.

dp[i][j][k] : (j, k)에 'i' state인 move 최솟값, (j, k)는 왼쪽 칸([left])을 기준

import java.util.*;

class Solution {
	class Robot {
		int ly, lx, ry, rx;
		int move, state;

		public Robot(int ly, int lx, int ry, int rx, int move, int state) {
			this.ly = ly;
			this.lx = lx;
			this.ry = ry;
			this.rx = rx;
			this.move = move;
			this.state = state;
		}
	}

	public int solution(int[][] board) {
		int N = board.length;
		/*
		 * 중복방지를 위해서 dp 사용
		 * dp[i][j][k] : (j, k)에 'i' state인 move 최솟값, (j, k)는 왼쪽 칸([l])을 기준
		 */
		int[][][] dp = new int[2][N][N];

        //큰 값으로 dp 초기화
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < N; ++k) {
					dp[i][j][k] = (int) 1e9;
				}
			}
		}

		Queue<Robot> queue = new LinkedList<>();
		queue.add(new Robot(0, 0, 0, 1, 0, 0));
		
		while (!queue.isEmpty()) {
			Robot rb = queue.poll();

			//왼쪽 칸 or 오른쪽 칸이 (N - 1, N - 1)이면 종료
			if ((rb.ly == N - 1 && rb.lx == N - 1) || (rb.ry == N - 1 && rb.rx == N - 1)) {
				return rb.move;
			}
			
			//현재 저장된 값보다 move가 크거나 같으면 진행 x
			if (dp[rb.state][rb.ly][rb.lx] <= rb.move) continue;
			//dp값 최솟값으로 갱신
			dp[rb.state][rb.ly][rb.lx] = rb.move;

			//state : 0  => [l][r]
			if (rb.state == 0) {
				if (rb.lx > 0 && board[rb.ly][rb.lx - 1] == 0) {
					//왼쪽으로 이동
					queue.add(new Robot(rb.ly, rb.lx - 1, rb.ly, rb.lx, rb.move + 1, 0));
				}

				if (rb.rx < N - 1 && board[rb.ry][rb.rx + 1] == 0) {
					//오른쪽으로 이동
					queue.add(new Robot(rb.ry, rb.rx, rb.ry, rb.rx + 1, rb.move + 1, 0));
				}

				if (rb.ly < N - 1 && (board[rb.ly + 1][rb.lx] == 0 && board[rb.ry + 1][rb.rx] == 0)) {
					//아래쪽으로 이동
					queue.add(new Robot(rb.ly + 1, rb.lx, rb.ry + 1, rb.rx, rb.move + 1, 0));
					//[l]를 축으로 [r]를 시계방향으로 회전
					queue.add(new Robot(rb.ly, rb.lx, rb.ly + 1, rb.lx, rb.move + 1, 1));
					//[r]를 축으로 [l]를 반시계방향으로 회전
					queue.add(new Robot(rb.ry, rb.rx, rb.ry + 1, rb.rx, rb.move + 1, 1));
				}

				if (rb.ly > 0 && (board[rb.ly - 1][rb.lx] == 0 && board[rb.ry - 1][rb.rx] == 0)) {
					//위쪽으로 이동
					queue.add(new Robot(rb.ly - 1, rb.lx, rb.ry - 1, rb.rx, rb.move + 1, 0));
					//[l]를 축으로 [r]를 반시계방향으로 회전
					queue.add(new Robot(rb.ly - 1, rb.lx, rb.ly, rb.lx, rb.move + 1, 1));
					//[r]를 축으로 [l]를 시계방향으로 회전
					queue.add(new Robot(rb.ry - 1, rb.rx, rb.ry, rb.rx, rb.move + 1, 1));
				}
			}
			//state : 1  =>  [l]
			//				 [r]
			else {
				if (rb.ly > 0 && board[rb.ly - 1][rb.lx] == 0) {
					//위쪽으로 이동
					queue.add(new Robot(rb.ly - 1, rb.lx, rb.ly, rb.lx, rb.move + 1, 1));
				}
				
				if (rb.lx > 0 && (board[rb.ly][rb.lx - 1] == 0 && board[rb.ry][rb.rx - 1] == 0)) {
					//왼쪽으로 이동
					queue.add(new Robot(rb.ly, rb.lx - 1, rb.ry, rb.rx - 1, rb.move + 1, 1));
				}

				if (rb.lx < N - 1 && (board[rb.ly][rb.lx + 1] == 0 && board[rb.ry][rb.rx + 1] == 0)) {
					//오른쪽으로 이동
					queue.add(new Robot(rb.ly, rb.lx + 1, rb.ry, rb.rx + 1, rb.move + 1, 1));
					//[l]를 축으로 [r]를 반시계방향으로 회전
					queue.add(new Robot(rb.ly, rb.lx, rb.ly, rb.lx + 1, rb.move + 1, 0));
					//[r]를 축으로 [l]를 시계방향으로 회전
					queue.add(new Robot(rb.ry, rb.rx, rb.ry, rb.rx + 1, rb.move + 1, 0));
				}

				if (rb.ry < N - 1 && board[rb.ry + 1][rb.rx] == 0) {
					//아래쪽으로 이동
					queue.add(new Robot(rb.ry, rb.rx, rb.ry + 1, rb.rx, rb.move + 1, 1));
				}

				if (rb.lx > 0 && (board[rb.ly][rb.lx - 1] == 0 && board[rb.ry][rb.rx - 1] == 0)) {
					//[l]를 축으로 [r]를 시계방향으로 회전
					queue.add(new Robot(rb.ly, rb.lx - 1, rb.ly, rb.lx, rb.move + 1, 0));
					//[r]를 축으로 [l]를 반시계방향으로 회전
					queue.add(new Robot(rb.ry, rb.rx - 1, rb.ry, rb.rx, rb.move + 1, 0));
				}
			}
		}

		return -1;
	}
}