[Programmers] 2020 카카오 블라인드 채용 7번 - 블록 이동하기

[문제 설명]

2차원 배열 board가 주어진다.

0은 비어있는 칸, 1은 막혀있는 칸이다.

맨 처음 (1,1) (1,2) 에 로봇이 놓여 있을 때, (N, N)까지 이동하는데 소요되는 최소 시간을 구하는 문제.

 

[조건]

5 <= len (board) <= 100

board의 원소는 0 또는 1

항상 목적지에 도착할 수 있는 경우만 입력으로 주어짐

 

[풀이 과정]

이차원 배열 위에서 최단 경로 및 최단 시간을 찾는 문제는 전형적인 BFS, DFS 문제이다.

따라서 어떤 알고리즘을 적용할지에 대한 고민은 하지 않았다.

 

다만, 기존의 문제와 다른 점은 2가지가 있었고, 해당 문제를 아래와 같이 접근하였다.

 

 

1. 로봇의 상태가 두 점을 차지한다는 것 -> 기준점을 잡고 해당 점 (+ 수평/수직 상태 변수) 으로 탐색

 

로봇이 수평으로 놓여있는 경우 -> 오른쪽 점을 기준으로 탐색
로봇이 수직으로 놓여있는 경우 -> 아래 점을 기준으로 탐색

ex)
(1, 1) (1, 2)의 로봇 -> (1, 2) 점 하나 + 수평 상태 (값 0)
(1, 1) (2, 1)의 로봇 -> (2, 1) 점 하나 + 수직 상태 (값 1)

 

2. 상, 하, 좌, 우의 이동 외에 회전이 가능하다는 것 -> 위에서 저장한 수평/수직 상태 변수에 따른 경우 나누기

 

<확인할 위치>

수평 상태에서 회전 가능 여부 -> 위 두 칸 && 아래 두 칸이 비어있는지
수직 상태에서 회전 가능 여부 -> 왼쪽 두 칸 && 오른쪽 두 칸이 비어있는지

 

이 두 가지에 유의하여 코드를 작성하였다.

 

import java.util.LinkedList;
import java.util.Queue;

public class Programmers_kakao2020_7 {
	static int boardSize;
	static class Info {
		int x, y, isVertical, cnt;
		
		Info(int x, int y, int isVertical, int cnt) {
			this.x = x;
			this.y = y;
			this.isVertical = isVertical;
			this.cnt = cnt;
		}
	}
	static int moveCheck[][][][] = {
			{                             // horizontal
				{{-1, 0}, {-1, -1}},      // 상
				{{1, 0}, {1, -1}},        // 하
				{{0, -2}},                // 좌
				{{0, 1}}                  // 우
			}, {                          // vertical
				{{-2, 0}},                // 상
				{{1, 0}},                 // 하 
				{{0, -1}, {-1, -1}},      // 좌 
				{{0, 1}, {-1, 1}}         // 우
			}
	};
	static int rotateCheck[][][][] = {
			{                             // horizontal
				{{0, 0}, {0, -1}},        // 위쪽
				{{1, 0}, {1, -1}}         // 아래쪽
			},{                           // vertical
				{{}},{{}},                // 이후 반복문 활용을 위해 비운 값
				{{0, 0}, {-1, 0}},        // 좌
				{{0, 1}, {-1, 1}}         // 우
			}
	};
	static int dir[][] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우
	
    public static int solution(int[][] board) {
        int answer = 0;
        boardSize = board.length;
        boolean[][][] visited = new boolean[boardSize][boardSize][2];
        
        visited[0][1][0] = true;           // [][][0] : horizontal, [][][1] : vertical
        Queue<Info> q = new LinkedList<>();
        
        q.add(new Info(0, 1, 0, 0));
        
        searching : while(!q.isEmpty()) {  // answer is always exists
        	Info cur = q.poll();
        	int cx = cur.x;
        	int cy = cur.y;
        	int cv = cur.isVertical;
        	int cc = cur.cnt;
        	int nx, ny, nv;
        	
    		for (int d = 0; d < 4; ++d) {   // 상, 하, 좌, 우  이동
    			boolean isAble = true;
    			
    			for (int a = 0; a < moveCheck[cv][d].length; ++a) {
    				nx = cx + moveCheck[cv][d][a][0];
    				ny = cy + moveCheck[cv][d][a][1];
    				
    				// 이동할 수 있는 경우
    				if (nx < 0 || ny < 0 || nx >= boardSize || ny >= boardSize || board[nx][ny] == 1) {
    					isAble = false;
    				}
    			}
    			
    			nx = cx + dir[d][0];
    			ny = cy + dir[d][1];
    			
    			// 이전에 탐색 안한 케이스인 경우
    			if (isAble && !visited[nx][ny][cv]) {
    				visited[nx][ny][cv] = true;
    				
    				if (nx == boardSize - 1 && ny == boardSize - 1) {
    					answer = cc + 1;
    					break searching;
    				}
    				
    				q.add(new Info(nx, ny, cv, cc + 1));
    			}
    		}
            
    		// 회전인 경우
    		int startD = (cv == 0) ? 0 : 2;
    		int endD = (cv == 0) ? 2 : 4;
    		
    		for (int d = startD; d < endD; ++d) {
    			boolean isAble = true;
    			
    			for (int a = 0; a < moveCheck[cv][d].length; ++a) {
    				nx = cx + moveCheck[cv][d][a][0];
    				ny = cy + moveCheck[cv][d][a][1];
    				
    				// 이동할 수 있는 경우
    				if (nx < 0 || ny < 0 || nx >= boardSize || ny >= boardSize || board[nx][ny] == 1) {
    					isAble = false;
    				}
    			}
    			
    			if (isAble) {
    				for (int a = 0; a < rotateCheck[cv][d].length; ++a) {
    					nx = cx + rotateCheck[cv][d][a][0];
    					ny = cy + rotateCheck[cv][d][a][1];
    					nv = (cv == 0) ? 1 : 0;
    					
    					if (!visited[nx][ny][nv]) {
    						visited[nx][ny][nv] = true;
    						if (nx == boardSize - 1 && ny == boardSize - 1) {
            					answer = cc + 1;
            					break searching;
            				}
    						q.add(new Info(nx, ny, nv, cc + 1));
    					}
    				}
    			}
    		}
        }
        return answer;
    }
    
   public static void main(String[] args) {
	   System.out.println(solution(new int[][] { {0, 0, 0, 1, 1},{0, 0, 0, 1, 0},{0, 1, 0, 1, 1},{1, 1, 0, 0, 1},{0, 0, 0, 0, 0} }));
   }
}

 

 

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

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