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

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60063

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

1. 주의할 점

- 구현해야 하는 조건이 많다

- 2개의 좌표를 어떤 방식으로 저장할 것인지 정한다

 

2. 구현

- BFS를 통해 문제를 해결한다

- Info 객체를 통해 로봇의 정보를 저장한다. 로봇의 한 좌표와 어떤 방향에 다른 좌표가 위치해 있는지 저장한다.

- 우선순위큐 pq에 로봇의 정보를 담으며, 소요 시간의 오름차순으로 정렬한다

- Board의 정보를 static 변수인 Arr[][]에 담아 모든 Method에서 파라미터로 받지 않아도 접근할 수 있도록 한다

- getVal() 함수를 통해 2개의 좌표에 대해 우선순위큐 pq2를 사용하여 정렬한다(Y의 오름차순>X의 오름차순). 그리고 2개의 좌표와 MAX를 활용하여 고유 값을 만들고 반환한다

- Cal() 함수를 통해 2개의 좌표에 방문한적이 없다면 Map에 추가하고 True를 반환한다. 방문한적이 있다면, 그보다 적은 시간으로 해당 좌표를 방문할 수 있다면 Map의 값을 수정하고 True를 반환한다. 이외의 경우는 전부 False를 반환한다

- Map<Long,Integer> map을 통해 2개의 좌표에 몇 시간만에 방문했는지 저장한다(<2개 좌표에 대한 고유값, 이동한 칸 수>)

- checkCanGo() 함수를 통해 해당 좌표로 이동 가능 유무를 판별한다

- calRot() 함수를 통해 로봇의 한 좌표를 축으로 잡고 다른 1개의 좌표를 기준으로 시계/반시계 방향으로 회전 가능하다면 필요한 시간을 저장한다. 도중에 막힌다면 Break를 통해 회전하지 못하도록 막는다

- move4Dir() 함수를 통해 로봇이 상하좌우로 움직이는 경우를 계산하며 checkCanGo()와 cal() 함수를 적절히 사용하여 계속해서 한 방향으로 나아갈 수 있다면 해당 위치를 pq에 담는다

 

import java.util.*;
import java.io.*;

class Solution {
    static class Info implements Comparable<Info>{
		int y, x, dir, val;

		public Info(int y, int x, int dir, int val) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.val = val;
		}
        
        @Override
        public int compareTo(Info o){
            return Integer.compare(this.val,o.val);
        }
	};

    static class Info2 implements Comparable<Info2>{
        int y,x;
        public Info2(int y, int x){
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(Info2 o){
            if(this.y==o.y) return Integer.compare(this.x,o.x);
            return Integer.compare(this.y,o.y);
        }
    };
    
	final static int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	final static int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	final static int MAX = 101;
    static int arr[][];
	static HashMap<Long,Integer> map;
	static int bigX, smallX, bigY, smallY, row, col;
	static int canRot[];
    static PriorityQueue<Info> pq;
    
    static long getVal(int x1, int y1, int x2, int y2){
        PriorityQueue<Info2> pq2 = new PriorityQueue<>();
        pq2.offer(new Info2(y1,x1));
        pq2.offer(new Info2(y2,x2));
        long first,sec;
        Info2 ii = pq2.poll();
        first = ii.x*MAX+ii.y;
        ii = pq2.poll();
        sec = ii.x*MAX+ii.y;
		long val = first * MAX * MAX + sec;
        return val;
    }
    
	static boolean cal(int y1, int x1, int y2, int x2, int sumVal) {
        long val = getVal(x1,y1,x2,y2);
		if (map.containsKey(val)){
            int originVal = map.get(val);
			if(originVal>sumVal) {
				map.put(val, sumVal);
				return true;
			}
			else return false;
		}
		else {
			map.put(val, sumVal);
			return true;
		}
	}
	
    static void calRot(int y, int x, int dir) {
		canRot = new int[8];
        for(int i=0;i<8;i++)
            canRot[i]=10;
		int cnt = 3;
		int nd = dir;
		int ny,nx,val=0;
		//시계방향
		while(cnt-->0) {
            val++;
			nd = (nd+1)%8;
			ny = y+ dy[nd];
			nx = x+ dx[nd];
			if(checkCanGo(ny,nx)) {
				nd = (nd+1)%8;
				ny = y+ dy[nd];
				nx = x+ dx[nd];
				if(checkCanGo(ny,nx)) {
					canRot[nd]=Math.min(canRot[nd],val);
				}
				else break;
			}
			else break;
		}
		cnt=3;
		nd=dir;
        val=0;
		//반시계
		while(cnt-->0) {
            val++;
			nd = (nd+7)%8;
			ny = y+ dy[nd];
			nx = x+ dx[nd];
			if(checkCanGo(ny,nx)) {
				nd = (nd+7)%8;
				ny = y+ dy[nd];
				nx = x+ dx[nd];
				if(checkCanGo(ny,nx)) {
					canRot[nd]=Math.min(canRot[nd],val);
				}
				else break;
			}
			else break;
		}
		
	}

	static boolean checkCanGo(int y, int x) {
		if(x >= 0 && y >= 0 && x < col && y < row && arr[y][x] == 0) return true;
		return false;
	}
	
    static void move4Dir(int y1, int x1, int y2, int x2, int val, int dir){
        for (int i = 0; i < 8; i += 2) {
            int nay = y1 + dy[i];
            int nax = x1 + dx[i];
            int nby = y2 + dy[i];
            int nbx = x2 + dx[i];
            int cnt = 1;
            while (true) {
                if (checkCanGo(nay, nax) && checkCanGo(nby, nbx)) {     //이동은 가능
                    //이미 존재하는지 확인
                    int nv = val + cnt;
                    if (cal(nay, nax, nby, nbx, nv)) {
                        pq.offer(new Info(nay,nax,dir,val+cnt));
                        nay += dy[i];
                        nax += dx[i];
                        nby += dy[i];
                        nbx += dx[i];
                        cnt++;
                    }
                    else break;
                }
                else break;
            }
        }
    }
    
	public static int solution(int[][] board) {
		int answer = 0;
		row = board.length;
		col = board[0].length;
        //초기화
        arr = new int[row][col];
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                arr[i][j]=board[i][j];
		map = new HashMap<>();
		pq = new PriorityQueue<>();
		pq.offer(new Info(0, 0, 2, 0));     //y,x,dir,val
		cal(0, 0, 0, 1, 0);

		while (!pq.isEmpty()) {
			Info ii = pq.poll();
			int cx = ii.x;
			int cy = ii.y;
			int cv = ii.val;
			int cd = ii.dir;
			int sx = ii.x + dx[cd];
			int sy = ii.y + dy[cd];
            //System.out.println("cy,cx,sy,sx,cv: " + cy + " " + cx + " " + sy + " " + sx + " " + cv);
			if ((cx == col - 1 && cy == row - 1) || (sx == col - 1 && sy == row - 1)) {
				answer = cv;
				break;
			}
			calRot(cy, cx, cd);
			for (int i = 0; i < 8; i += 2) {
				if (i == cd || canRot[i]==10)	continue;
				int nsx = cx + dx[i];
				int nsy = cy + dy[i];
				if (checkCanGo(nsy,nsx)) {
					if (cal(nsy, nsx, cy, cx,cv+canRot[i]))
						pq.offer(new Info(cy, cx, i, cv + canRot[i]));
				}
			}
			calRot(sy, sx, (cd+4)%8);
			for (int i = 0; i < 8; i += 2) {
				int nd = (i + 4) % 8;
				if (nd == cd || canRot[i]==10) continue;
				int nx = sx + dx[i];
				int ny = sy + dy[i];
				if (checkCanGo(ny,nx)) {
					if (cal(ny, nx, sy, sx,cv+canRot[i]))
						pq.offer(new Info(sy, sx, i, cv + canRot[i]));
				}
			}
			
			//상하좌우
			move4Dir(cy,cx,sy,sx,cv,cd);
		}
		return answer;
	}
}