[프로그래머스] 2020 카카오 #7 블록 이동하기 (Java)

#7 블록 이동하기

난이도 : LEVEL 3

유형 : BFS, 시뮬레이션 

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

▸ 문제

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

 

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

 

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

 

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

▸ 제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

 

문제 풀이  

이번 기출에는 빡구현문제가 많은 것 같다. 설계는 사실상 로봇 움직임에 대해서만 고민해주면 되므로 금방 끝냈는데 구현에서 많이 헤맸다. 로봇 회전하는 부분에서 오타도 많았고 놓친 조건 부분도 있었다. 5번 문제도 그렇고 이런 문제가 나오면 조건문을 진짜 신중히 다뤄줘야 함을 느꼈다.

 

설계 및 구현

시작점에서 (n,n)으로 도착하는 최단 거리를 구하는 문제이므로 BFS탐색이 베이스로 깔려야한다. 이제 그 BFS내부에서 로봇의 움직임들을 고려해서 탐색을 진행해주면 된다.

1. 상하좌우 이동

상하좌우 이동은 그냥 기본 BFS탐색처럼 각 방향으로 한 칸씩 움직이면 된다. 

 

2. 로봇 회전

이 부분이 이 문제의 난이도를 올려주는 곳이다. 로봇의 상태와 회전 방향과 회전이 되는 축 총 3가지를 고려해줘야 하기 때문이다. 그리고 구현을 하다보니 깨달은 것인데 축에 상관없이 회전하는 방향이 같다면 고려해야할 좌표가 같다는 것이다.회전에 대한 조건 메소드만 구현하면 해당 문제는 끝이다.

 

위로 회전할 때

 

그러면 다음과 같이 구현할 수 있다.

1. 로봇의 현재 상태(pStatus)를 확인한다. (가로0 / 세로1)
2. 각 상태에 따라 (상/하/좌/우) 방향으로 회전을 해준다.
   1. 각 방향에 대해 움직여야 할 블록을 탐색하여 벽이 있는지 조사한다. boolean graphCondition(int x1, int y1, int x2, int y2);
   2. 1번이 true라면 해당 방향으로 (앞축/ 뒷축)을 회전시켜 다음 탐색을 진행한다.
3. 앞축/뒷축 상관없이 (n,n)에 도착한다면 탐색을 종료한다. if((pbx == size-1 && pby==size-1)
   || (pfx == size-1 && pfy==size-1))

// 로봇 가로 상태
if(pStatus==0) {
	// 위로 회전 
	if(graphCondition(pbx, pby-1, pfx, pfy-1)) {
		// 앞축고정 회전(위로 90)
		q.add(new Robot(pfx, pfy, pfx, pfy-1, 1, mv+1));
		// 뒤축고정 회전(위로 90)
		q.add(new Robot(pbx, pby, pbx, pby-1, 1, mv+1));
	}

	// 아래로 회전 
	if(graphCondition(pbx, pfy+1, pfx, pfy+1)) {
		// 앞축고정 회전(아래로 90)
		q.add(new Robot(pfx, pfy, pfx, pfy+1, 1, mv+1));
		// 뒤축고정 회전(아래로 90)
		q.add(new Robot(pbx, pby, pbx, pby+1, 1, mv+1));
	}
}
// 로봇 세로 상태
else if(pStatus==1) {
	// 오른쪽 회전 
	if(graphCondition(pbx+1, pby, pfx+1, pfy)) {
		// 앞축고정 회전 (오른쪽 90)
		q.add(new Robot(pfx, pfy, pfx+1, pfy, 0, mv+1));
		// 뒤축고정 회전 (오른쪽 90)
		q.add(new Robot(pbx, pby, pbx+1, pby, 0, mv+1));
	}
  	// 왼쪽 회전 
  	if(graphCondition(pbx-1, pby, pfx-1, pfy)) {
  		// 앞축고정 회전 (왼쪽 90)
  		q.add(new Robot(pfx, pfy, pfx-1, pfy, 0, mv+1));
  		// 뒤축고정 회전 (왼쪽  90)
  		q.add(new Robot(pbx, pby, pbx-1, pby, 0, mv+1));
  	}
}

 

 

풀이 코드 

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

class Solution {
    static int size;
	static int[][] map;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
    public int solution(int[][] board) {
        int answer = 0;
        size = board.length;	
        map = board;
        answer =  bfs();
        return answer;
    }
	
	static int bfs() {
		Queue<Robot> q = new LinkedList<>();
		boolean[][][] check = new boolean[size][size][2];
		q.add(new Robot(0,0,1,0,0,0));
		
		while(!q.isEmpty()) {
			Robot robot = q.poll();
			int pbx = robot.bx, pby =robot.by;
			int pfx = robot.fx, pfy =robot.fy;
			int pStatus = robot.status;
			int mv = robot.move;
			
			if(check[pby][pbx][pStatus] && check[pfy][pfx][pStatus]) continue;
			check[pby][pbx][pStatus] = true;
			check[pfy][pfx][pStatus] = true;
			
			if((pbx == size-1 && pby==size-1)
					|| (pfx == size-1 && pfy==size-1)) {
				return mv;
			}
			// 1. 상하좌우 이동 
			for(int d=0; d<4; d++) {
				int nbx = pbx+dx[d];
				int nby = pby+dy[d];
				int nfx = pfx+dx[d];
				int nfy = pfy+dy[d];
				
				if(graphCondition(nbx, nby, nfx, nfy)) {
						q.add(new Robot(nbx, nby, nfx, nfy, pStatus, mv+1));
				}
			}
			
			
			// 2. 90도 회전
			// 로봇 가로 상태
			if(pStatus==0) {
				// 위로 회전 
				if(graphCondition(pbx, pby-1, pfx, pfy-1)) {
						// 앞축고정 회전(위로 90)
						q.add(new Robot(pfx, pfy, pfx, pfy-1, 1, mv+1));
						// 뒤축고정 회전(위로 90)
						q.add(new Robot(pbx, pby, pbx, pby-1, 1, mv+1));
				}
				
				// 아래로 회전 
				if(graphCondition(pbx, pfy+1, pfx, pfy+1)) {
						// 앞축고정 회전(아래로 90)
						q.add(new Robot(pfx, pfy, pfx, pfy+1, 1, mv+1));
						// 뒤축고정 회전(아래로 90)
						q.add(new Robot(pbx, pby, pbx, pby+1, 1, mv+1));
				}
				
			}
			// 로봇 세로 상태
			else if(pStatus==1) {
				// 오른쪽 회전 
				if(graphCondition(pbx+1, pby, pfx+1, pfy)) {
					// 앞축고정 회전 (오른쪽 90)
						q.add(new Robot(pfx, pfy, pfx+1, pfy, 0, mv+1));
						// 뒤축고정 회전 (오른쪽 90)
						q.add(new Robot(pbx, pby, pbx+1, pby, 0, mv+1));
				}
				
				// 왼쪽 회전 
				if(graphCondition(pbx-1, pby, pfx-1, pfy)) {
						// 앞축고정 회전 (왼쪽 90)
						q.add(new Robot(pfx, pfy, pfx-1, pfy, 0, mv+1));
						// 뒤축고정 회전 (왼쪽  90)
						q.add(new Robot(pbx, pby, pbx-1, pby, 0, mv+1));
				}
				
			}
		}
		return -1;
	}
	
	
	static boolean graphCondition(int x1, int y1, int x2, int y2) {
		if(x1 <0 || x2 <0 || x1>size-1 || x2>size-1
				|| y1<0 || y2<0 || y1>size-1 || y2>size-1
				|| map[y1][x1] ==1 || map[y2][x2] ==1) return false;
		
		return true;
	}
	
	static class Robot{
		int bx;
		int by;
		int fx;
		int fy;
		int status; // 0 가로, 1 세로 
		int move;
		
		public Robot(int bx, int by, int fx, int fy, int status, int move) {
			this.bx = bx;
			this.by = by;
			this.fx = fx;
			this.fy = fy;
			this.status = status;
			this.move = move;
		}
	}
}