[프로그래머스(Programmers)][자바(java)] (Lv3) 블록 이동하기

 

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

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

 

문제 요약

• 빈 칸( "0" )과 벽( "1" )으로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (1, 1)에서 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하는 함수 작성
• 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다.
• 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.
• 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.
• 로봇은 90도씩 회전할 수 있습니다.
  단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다.
• 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

 

문제 풀이

*  BFS

-  보드판( int[][] board )의 한 변의 길이( int n ) 구함

-  로봇 클래스( class Robot ) 생성
    -  현재 좌표 ( x, y )
    -  로봇이 현재 모양이 가로인지 세로인지의 상태( int h ☞ 0이면 가로, 1이면 세로 ) ( h : horizontal )
    -  소요 시간(초)( 이동+회전 횟수와 같음 )( int s ) ( s : second )

-  지도 안에서 길을 BFS 하며 로봇을 이동/회전

-  ( 0, 0 )에서 시작하며, 가로 모양이고 ( n-1, n-2 )이거나 세로 모양이고 ( n-2, n-1 )이면 BFS 종료

-  최소 시간을 구하려면 도착 지점에 처음 도달했을 때의 소요 시간을 바로 리턴하면 됨
   따라서 이미 방문한 좌표는 다시 방문할 필요 없음

-  해당 좌표에 방문했는지 상태를 저장할 배열 생성( boolean v[][][] ) ( v : visited ) 
   로봇이 가로일 때와 세로일 때를 별개로 고려하기 위해 3차원으로 생성

현재 좌표 ( x, y )는 l1 기준

색을 달리한 이유는 더 왼쪽인, 위쪽인 좌표를 l1로 했다는 것을 표시하기 위헤

import java.util.*;

public class Solution {
	
	class Robot {
		int x, y, h, s;  // x, y, horizontal( 0 : h, 1 : v ), second
		Robot( int x, int y, int h, int s ) {
			this.x = x;
			this.y = y;
			this.h = h;
			this.s = s;
		}
	}
	
	public int solution(int[][] board) {
		int n = board.length;  // n : width
		int x, y, s, h, ns, nh;  // next
		boolean v[][][] = new boolean[n][n][2];
		Queue<Robot> q = new LinkedList<>();
		q.add( new Robot( 0, 0, 0, 0 ) );
		Robot rb;
		while( !q.isEmpty() ) {
			rb = q.remove();
			x = rb.x; y = rb.y; s = rb.s; h = rb.h;
			if( ( x == n-1 && y == n-2 && h == 0 ) || ( x == n-2 && y == n-1 && h == 1 ) ) 
				return s;
			if( v[x][y][h] )
				continue;
			v[x][y][h] = true;
			ns = s+1; nh = h == 0 ? 1 : 0;
			if( h == 0 ) {
				if( y < n-2 && board[x][y+2] == 0 && !v[x][y+1][h] )	q.add( new Robot( x, y+1, h, ns ) );
				if( y > 0 && board[x][y-1] == 0 && !v[x][y-1][h] )		q.add( new Robot( x, y-1, h, ns ) );
				if( x < n-1 && y < n-1 && board[x+1][y] == 0 && board[x+1][y+1] == 0 ) {
					if( !v[x+1][y][h] )				q.add( new Robot( x+1, y, h, ns ) );
					if( !v[x][y][nh] ) 				q.add( new Robot( x, y, nh, ns ) );
					if( !v[x][y+1][nh] ) 			q.add( new Robot( x, y+1, nh, ns ) );
				}
				if( x > 0 && y < n-1 && board[x-1][y] == 0 && board[x-1][y+1] == 0 ) {
					if( !v[x-1][y][h] )				q.add( new Robot( x-1, y, h, ns ) );
					if( !v[x-1][y][nh] )			q.add( new Robot( x-1, y, nh, ns ) );
					if( !v[x-1][y+1][nh] )			q.add( new Robot( x-1, y+1, nh, ns ) );
				}
			}
			else {
				if( x < n-2 && board[x+2][y] == 0 && !v[x+1][y][h] )	q.add( new Robot( x+1, y, h, ns ) );
				if( x > 0 && board[x-1][y] == 0 && !v[x-1][y][h] )		q.add( new Robot( x-1, y, h, ns ) );
				if( x < n-1 && y < n-1 && board[x][y+1] == 0 && board[x+1][y+1] == 0 ) {
					if( !v[x][y+1][h] )				q.add( new Robot( x, y+1, h, ns ) );
					if( !v[x][y][nh] )				q.add( new Robot( x, y, nh, ns ) );
					if( !v[x+1][y][nh] )			q.add( new Robot( x+1, y, nh, ns ) );
				}
				if( x < n-1 && y > 0 && board[x][y-1] == 0 && board[x+1][y-1] == 0 ) {
					if( !v[x][y-1][h] )				q.add( new Robot( x, y-1, h, ns ) );
					if( !v[x][y-1][nh] )			q.add( new Robot( x, y-1, nh, ns ) );
					if( !v[x+1][y-1][nh] )			q.add( new Robot( x+1, y-1, nh, ns ) );
				}	
			}
		}
		return -1;
	}

}