[JAVA] 프로그래머스 LEVEL3 블록 이동하기

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

프로그래머스

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 블록 이동하기

 

난이도: LEVEL3

알고리즘 유형:  구현 

 

회전 로직 구현이 너무 힘들었다... 

 

내가 했던 실수 

방문 표시를 하는데 

가로면 왼쪽 좌표 오른쪽 좌표 순서대로 모두 더해서 String으로 만들어서 Set<String>에 저장

세로면 위 아래 순서대로 더해서 Set에 저장

 

이렇게 하면 좌표 구별이 안된다. 

ex) (11, 1) (12, 3) 111123 → (1, 11) (12, 3) 해당 케이스로 인식 가능 

그래서 좌표 중간에 "-"를 추가하여 유일한 값으로 바꾸었다.

 

2개의 좌표 방문 기록에 대한 더 좋은 방법을 생각해 봤는데 딱히 떠오르지가 않는다. 

정답 코드

import java.util.*;
class Solution {
    static int [] arx = {-1,1,0,0}; // 위 아래 좌 우 
    static int [] ary = {0,0,-1,1};
    static int n,m;
    static Queue<int[]> q = new LinkedList<>();
    static HashSet<String> set = new HashSet<>();
    static ArrayList<int[]> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder ();
    public int solution(int[][] board) {
        n = board.length; // 행 
        m = board[0].length; // 열 
        set.add("0-0-0-1"); // 시작 지점 
        q.add(new int []{0,0,0,1,0});
        while(!q.isEmpty()){
            int [] temp = q.poll();
            // 상하좌우 이동 
            for(int i = 0; i < 4; i++){
                int nx1 = temp[0] + arx[i];
                int ny1 = temp[1] + ary[i];
                int nx2 = temp[2] + arx[i];
                int ny2 = temp[3] + ary[i];
                if(!validation(nx1, ny1, nx2, ny2)) continue;
                if(board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue;
                if(isArrive(nx1, ny1, nx2, ny2)){
                    return temp[4] + 1;
                }
                addLogic(nx1, ny1, nx2, ny2, temp[4]);
            }
            // 회전
            int nx1 = 0; int ny1 = 0;
            int nx2 = 0; int ny2 = 0;
            // 가로 -> 세로 
            if(temp[0] == temp[2]){
                for(int i = 0; i <= 1; i++){
                    nx1 = temp[0] + arx[i];
                    ny1 = temp[1] + ary[i];
                    nx2 = temp[2] + arx[i];
                    ny2 = temp[3] + ary[i];
                    if(!validation(nx1, ny1, nx2, ny2)) continue;
                    if(board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue;
                    if(isArrive(nx1, ny1, nx2, ny2)){
                        return temp[4] + 1;
                    }
                    // 회전 가능한 상태 
                    int nx_1 = 0;
                    int ny_1 = 0;
                    int nx_2 = 0;
                    int ny_2 = 0;
                    nx_1 = temp[0];
                    ny_1 = temp[1];
                    nx_2 = nx1;
                    ny_2 = ny1;
                    addLogic(nx_1, ny_1, nx_2, ny_2, temp[4]);
                    nx_1 = temp[2];
                    ny_1 = temp[3];
                    nx_2 = nx2;
                    ny_2 = ny2;
                    addLogic(nx_1, ny_1, nx_2, ny_2, temp[4]);
                }
            }
            // 세로 -> 가로 
            if(temp[1] == temp[3]){
                for(int i = 2; i <= 3; i++){
                    nx1 = temp[0] + arx[i];
                    ny1 = temp[1] + ary[i];
                    nx2 = temp[2] + arx[i];
                    ny2 = temp[3] + ary[i];
                    if(!validation(nx1, ny1, nx2, ny2)) continue;
                    if(board[nx1][ny1] == 1 || board[nx2][ny2] == 1) continue;
                    if(isArrive(nx1, ny1, nx2, ny2)){
                        return temp[4] + 1;
                    }
                    // 회전 가능한 상태 
                    int nx_1 = 0;
                    int ny_1 = 0;
                    int nx_2 = 0;
                    int ny_2 = 0;
                    nx_1 = temp[0];
                    ny_1 = temp[1];
                    nx_2 = nx1;
                    ny_2 = ny1;
                    addLogic(nx_1, ny_1, nx_2, ny_2, temp[4]);
                    nx_1 = temp[2];
                    ny_1 = temp[3];
                    nx_2 = nx2;
                    ny_2 = ny2;
                    addLogic(nx_1, ny_1, nx_2, ny_2, temp[4]);
                }
            }
        }
        return 0;
    }
    // 방문을 가록하는 메소드 
    public static void addLogic(int nx1, int ny1, int nx2, int ny2, int cnt){
        list.clear();
        sb.setLength(0);

        list.add(new int [] {nx1, ny1});
        list.add(new int [] {nx2, ny2});
        list.sort((o1,o2) -> {
            if(o1[0] != o2[0]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });
        sb.append(list.get(0)[0]).append("-").append(list.get(0)[1])
            .append("-").append(list.get(1)[0])
            .append("-").append(list.get(1)[1]);

        String key = sb.toString();

        if(!set.contains(key)){
            set.add(key);
            q.add(new int [] {list.get(0)[0], list.get(0)[1], 
                              list.get(1)[0], list.get(1)[1], cnt + 1});    
        }
    }
    // 도착 여부 판별 메소드 
    public static boolean isArrive(int nx1, int ny1, int nx2, int ny2){
        if(nx1 == n - 1 && ny1 == m - 1) return true;
        if(nx2 == n - 1 && ny2 == m - 1) return true;
        return false;
    }
    // ArrayOutOfIndex 검사 메소드 
    public static boolean validation(int nx1, int ny1, int nx2, int ny2){
        if(nx1 < 0 || nx2 < 0 || ny1 < 0 || ny2 < 0) return false;
        if(nx1 >= n || nx2 >= n) return false;
        if(ny1 >= m || ny2 >= m) return false;
        return true;
    }
}