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

 

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

 

 

약 1.4%의 정답률인 문제입니다.

단순 구현 + BFS로 풀 수 있는 문제였습니다.

 

로봇이 가로일 때와 세로일 때의 방문 체크 배열을 따로 만들어서 체크해줬습니다.

로봇이 앞, 뒤로만 움직이는 줄 알았는데 4방향 모두 움직일 수 있었습니다.

이것 때문에 삽질만 1시간은 한 것 같네요.

 

파란색이 로봇의 현상태라 한다면, 초록색으로 회전을 해야 합니다.

현 상태에서 회전 가능한 경우의 수는 위로 2개, 밑으로 2개 총 4개입니다.

 

구현 문제라 코드로 이해해보세요.

---

전역 변수

map [][] = 지도

n = 지도의 크기

dx, dy = 상, 하, 좌, 우를 이동하기 위한 배열

row [][] = 로봇이 가로일 때 방문 체크

col [][] = 로봇이 세로일 때 방문 체크

answer = 목적지까지의 턴 수

메소드

int solution

전역 변수 값의 초기 값을 세팅해줍니다. 로봇의 초기 위치를 방문 체크해준 후 시작합니다.

(start 호출)

 

void start

BFS를 시작합니다. 로봇의 dir이 -1이면 한 턴이 끝났다는 것이므로 count를 증가시킵니다.

현재 로봇의 위치가 목적지라면 answer 값을 최신화시킨 후 종료합니다.

로봇이 가로일 때 4방향 중 이동 가능한 방향이 있다면 Queue에 넣습니다.

그리고 회전이 가능하다면 회전한 상태를 Queue에 넣습니다.

큐에 넣기 전 방문 체크를 꼭 해줍니다. 

 

boolean rotate

로봇이 회전할 좌표를 넣고 회전이 가능한지 검사합니다.

 

boolean check

들어온 좌표값이 정상 범위이고 빈 공간(0)인지 검사합니다.

 

class Robot

로봇의 좌표 2개와 가로, 세로를 결정하는 방향을 가집니다.

dir = 0이면 가로, dir = 1이면 세로입니다.

 

class Point

x, y좌표를 저장하는 클래스입니다.

 

import java.util.*;

public class Solution{

	public int map[][];
	public int n;
	public int dx[] = {-1,1,0,0};
	public int dy[] = {0,0,-1,1};
	public boolean row[][];
	public boolean col[][];
	public int answer;

	public int solution(int[][] board) {
		n = board.length;
		answer = 0;
		row = new boolean[n][n];
		col = new boolean[n][n];
		map = new int[n][n];
		for(int i = 0; i < n; i++)
			map[i] = board[i].clone();

		row[0][0] = true;
		row[0][1] = true;

		start();

		return answer;
	}

	public void start() {
		Queue<Robot> q = new LinkedList<Robot>();
		q.add(new Robot(new Point(0,0), new Point(0,1), 0));
		q.add(new Robot(null, null, -1));
		int count = 0;

		while(!q.isEmpty()) {
			Robot now = q.poll();

			if(now.dir == -1) {
				count++;
				if(!q.isEmpty())
					q.add(new Robot(null, null, -1));
				continue;
			}
			
			if((now.p1.x == n-1 && now.p1.y == n-1) || (now.p2.x == n-1 && now.p2.y == n-1)) {
				answer = count;
				break;
			}

			if(now.dir == 0) {
				for(int i = 0; i < 4; i++) {
					int np1X = now.p1.x + dx[i];
					int np1Y = now.p1.y + dy[i];
					int np2X = now.p2.x + dx[i];
					int np2Y = now.p2.y + dy[i];

					if(check(np1X, np1Y) && check(np2X, np2Y)) {
						if(!row[np1X][np1Y] || !row[np2X][np2Y]) {
							Robot next = new Robot(new Point(np1X, np1Y), new Point(np2X, np2Y), 0);
							row[np1X][np1Y] = true;
							row[np2X][np2Y] = true;
							q.add(next);
						}
					}
				}

				for(int i = -1; i <= 1; i+=2) {
					int np1X = now.p1.x + i;
					int np1Y = now.p1.y;
					int np2X = now.p2.x + i;
					int np2Y = now.p2.y;

					if(check(np1X, np1Y) && check(np2X, np2Y)) {
						if(rotate(np1X, np1Y, now.p1.x, now.p1.y) && (!col[np1X][np1Y] || !col[now.p1.x][now.p1.y])) {
							col[np1X][np1Y] = true;
							col[now.p1.x][now.p1.y] = true;
							q.add(new Robot(new Point(np1X, np1Y), new Point(now.p1.x, now.p1.y), 1));
						}
						if(rotate(np2X, np2Y, now.p2.x, now.p2.y) && (!col[np2X][np2Y] || !col[now.p2.x][now.p2.y])) {
							col[np2X][np2Y] = true;
							col[now.p2.x][now.p2.y] = true;
							q.add(new Robot(new Point(np2X, np2Y), new Point(now.p2.x, now.p2.y), 1));
						}
					}
				}
			}
			else {
				for(int i = 0; i < 4; i++) {
					int np1X = now.p1.x + dx[i];
					int np1Y = now.p1.y + dy[i];
					int np2X = now.p2.x + dx[i];
					int np2Y = now.p2.y + dy[i];

					if(check(np1X, np1Y) && check(np2X, np2Y)) {
						if(!col[np1X][np1Y] || !col[np2X][np2Y]) {
							Robot next = new Robot(new Point(np1X, np1Y), new Point(np2X, np2Y), 1);
							col[np1X][np1Y] = true;
							col[np2X][np2Y] = true;
							q.add(next);
						}
					}
				}

				for(int i = -1; i <= 1; i+=2) {
					int np1X = now.p1.x;
					int np1Y = now.p1.y + i;
					int np2X = now.p2.x;
					int np2Y = now.p2.y + i;

					if(check(np1X, np1Y) && check(np2X, np2Y)) {
						if(rotate(np1X, np1Y, now.p1.x, now.p1.y) && (!row[np1X][np1Y] || !row[now.p1.x][now.p1.y])) {
							row[np1X][np1Y] = true;
							row[now.p1.x][now.p1.y] = true;
							q.add(new Robot(new Point(np1X, np1Y), new Point(now.p1.x, now.p1.y), 0));
						}
						if(rotate(np2X, np2Y, now.p2.x, now.p2.y) && (!row[np2X][np2Y] || !row[now.p2.x][now.p2.y])) {
							row[np2X][np2Y] = true;
							row[now.p2.x][now.p2.y] = true;
							q.add(new Robot(new Point(np2X, np2Y), new Point(now.p2.x, now.p2.y), 0));
						}
					}
				}
			}
		}
	}

	public boolean rotate(int x1, int y1, int x2, int y2) {
		if(!check(x1, y1) || !check(x2, y2))
			return false;

		return true;
	}

	public boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < n && y < n && map[x][y] == 0;
	}

	class Robot {
		Point p1, p2;
		int dir;
		Robot(Point p1, Point p2, int dir){
			this.p1 = p1;
			this.p2 = p2;
			this.dir = dir;
		}
	}

	class Point {
		int x, y;
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}