[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 블록이동하기

문제보기

실제 시험때는 시간부족으로 읽지도 못했던 문젭니다 ㅠㅠ
BFS를 이용해 이동해주면서 최소시간을 구해주면 됩니다~!

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

class Loc{
	int x; // 행
	int y; // 열
	int t; // 소요시간
	int p; // 포지션 : 0은 가로 1은 세로
	Loc(int x, int y, int t, int p){
		this.x = x;
		this.y = y;
		this.t = t;
		this.p = p;
	}
}

class Solution {
    static int[][] map;
	static int n;
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static int[] rowToColDx = {-1, -1, 0, 0};
	static int[] rowToColDy = {0, 1, 0, 1};
	static int[] colToRowDx = {0, 1, 0, 1};
	static int[] colToRowDy = {0, 0, -1, -1};
	
	static int bfs() {
		Queue<Loc> q = new LinkedList<Loc>();
		q.add(new Loc(0, 0, 0, 0)); // 첫 위치를 넣어줌 
		int[][][] visited = new int[n][n][2]; // i, j에서 각 포지션(0, 1)에 따른 최소 도달 시간을 기록할 배열 
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				Arrays.fill(visited[i][j], 999999); // 큰 수로 초기화
			}
		}
		
		visited[0][0][0] = 0; // 처음 위치는 0초 
		
		int min = Integer.MAX_VALUE;
		
		while(!q.isEmpty()) {
			Loc loc = q.remove();
			int x = loc.x;
			int y = loc.y;
			int t = loc.t;
			int p = loc.p;
			
			// 만일 (n,n)에 도착했다면 최소시간을 갱신합니다 
			if((x == n-1 && y == n-2 && p == 0) 
					|| (x == n-2 && y == n-1 && p == 1)) {
				if(t < min) min = t;
			}
			
			// 회전 없이 우좌하상으로 움직일때
			for(int k = 0 ; k < 4 ; k++) {
				if(k == 0) {
					if(!canGoRight(x, y, p)) continue;
				}else if(k == 1) {
					if(!canGoLeft(x, y, p)) continue;
				}else if(k == 2) {
					if(!canGoDown(x, y, p)) continue;
				}else {
					if(!canGoUp(x, y, p)) continue;
				}
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(visited[nx][ny][p] > t+1) {
					visited[nx][ny][p] = t+1;
					q.add(new Loc(nx, ny, t+1, p));
				}
				
			}
			// 가로로 놓인 상황인 경우 세로로 돌려보자 
			if(p == 0) {
				for(int k = 0 ; k < 4 ; k++) {
					if(k < 2) {
						if(!canRotateUp(x, y)) continue; // 돌려서 윗칸을 침범하는 세로모양으로 만들기
					}else {
						if(!canRotateDown(x, y)) continue; // 돌려서 아랫칸을 침범하는 세로모양으로 만들기
					}
					int nx = x + rowToColDx[k];
					int ny = y + rowToColDy[k];
					if(visited[nx][ny][1] > t+1) {
						visited[nx][ny][1] = t+1;
						q.add(new Loc(nx, ny, t+1, 1));
					}
				}
			}
			// 세로로 놓인 상황인 경우 가로로 돌려보자
			if(p == 1) {
				for(int k = 0 ; k < 4 ; k++) {
					if(k < 2) {
						if(!canRotateRight(x, y)) continue; // 돌려서 오른쪽칸을 침범
					}else {
						if(!canRotateLeft(x, y)) continue; // 돌려서 왼쪽칸을 침범 
					}
					int nx = x + colToRowDx[k];
					int ny = y + colToRowDy[k];
					if(visited[nx][ny][0] > t+1) {
						visited[nx][ny][0] = t+1;
						q.add(new Loc(nx, ny, t+1, 0));
					}
				}
			}
		}
		
		return min;
		
	}
	
	// 이 아래는 각각 맵 상황을 보고 움직일 수 있는지 여부를 판단해줄 메서드입니다.
	// 좀 더 머리를 쓰면 코드를 줄일 수 있을것 같긴 합니다만... 풀어서 적는게 때로는 이해가 빠를때도 있으니까요!(...)

	static boolean canGoRight(int x, int y, int p) {
		if(p == 0) {
			if(y+2 >= n || map[x][y+1] == 1 || map[x][y+2] == 1) 
				return false;
		}else {
			if(y+1 >= n || x+1 >= n || map[x][y+1] == 1 || map[x+1][y+1] == 1) 
				return false;
		}
		return true;
	}
	static boolean canGoLeft(int x, int y, int p) {
		if(p == 0) {
			if(y-1 < 0 || map[x][y-1] == 1)
				return false;
		}else {
			if(y-1 < 0 || x+1 >= n || map[x][y-1] == 1 || map[x+1][y-1] == 1)
				return false;
		}
		return true;
	}
	static boolean canGoDown(int x, int y, int p) {
		if(p == 0) {
			if(x+1 >= n || y+1 >= n || map[x+1][y] == 1 || map[x+1][y+1] == 1)
				return false;
		}else {
			if(x+2 >= n || map[x+1][y] == 1 || map[x+2][y] == 1) {
				return false;
			}
		}
		return true;
	}
	static boolean canGoUp(int x, int y, int p) {
		if(p == 0) {
			if(x-1 < 0 || y+1 >= n || map[x-1][y] == 1 || map[x-1][y+1] == 1)
				return false;
		}else {
			if(x-1 < 0 || map[x-1][y] == 1) {
				return false;
			}
		}
		return true;
	}
	
	static boolean canRotateUp(int x, int y) {
		if(x-1 < 0 || y+1 >= n || map[x-1][y] == 1 || map[x-1][y+1] == 1)
			return false;
		return true;
	}
	static boolean canRotateDown(int x, int y) {
		if(x+1 >= n || y+1 >= n|| map[x+1][y] == 1 || map[x+1][y+1] == 1)
			return false;
		return true;
	}
	static boolean canRotateRight(int x, int y) {
		if(y+1 >= n || x+1 >= n || map[x][y+1] == 1 || map[x+1][y+1] == 1)
			return false;
		return true;
	}
	static boolean canRotateLeft(int x, int y) {
		if(y-1 < 0 || x+1 >= n || map[x][y-1] == 1 || map[x+1][y-1] == 1)
			return false;
		return true;
	}
	
	public int solution(int[][] board) {
		map = board;
		n = board.length;
		
        return bfs();
    }
}