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

프로그래머스 블록 이동하기

문제풀이

알고리즘은 친숙한 BFS지만 구현이 굉장히 까다로운 문제였다. 이 블로그를 참조했다.

• (r1, c1)(r2, c2)와 (r2, c2)(r1, c1)은 같다.
• 내부 코드가 굉장히 복잡하기 때문에 배열 이탈 검사를 하기보다는 패딩을 주는 것이 좋다.
• 경우는 다음과 같다.
  • 회전하지 않고 상, 하, 좌, 우로 이동하기
  • 가로 상태에서 회전하기(한쪽을 축으로 시계, 반시계)
    • 아래쪽 두 칸이 모두 0이어야 아래쪽으로 회전 가능
    • 위쪽 두 칸이 모두 0이어야 위쪽으로 회전 가능
  • 세로 상태에서 회전하기(한 쪽을 축으로 시계, 반시계)
    • 왼쪽 두 칸이 모두 0이어야 왼쪽으로 회전 가능
    • 오른쪽 두 칸이 모두 0이어야 오른쪽으로 회전 가능

방문체크가 잘 안되서 오래걸렸다. 다음과 같은 시도를 해보았다.

• int형 hashCode를 직접 만들어 보았다. (HashMap)
  • r1 * 100 + c1 * 10 + r2 * 100 + c2 * 10
  • r1 * r2 + c1 * c2
  • 위와 같은 방식으로 만들어보았지만 몇가지 케이스를 통과하지 못했다.
  • 실험 결과 굉장히 많은 해시충돌을 보인다.
  • 하나의 좌표를 가지고 만들면 r1 * len + c1을 하면 된다. (10만 안쪽으로)
• String형 hashCode를 직접 만들어 보았다. (HashMap)
  • `"" + r1 + c1 + r2 + c2``
  • 위에서 틀리던 케이스는 맞았으나 다른 케이스가 틀렸다.
  • "" + r1 + ":" + c1 + ":" + r2 + ":" + c2와 같은 형태로 하면 해시코드의 중복을 막을 수 있으나 String을 다루는 것은 느리다.
• int형 4차원 배열로 방문체크를 했다.
  • 통과하였으나 굉장히 느렸다.
• Node 객체의 hashCode와 equals를 오버라이딩 했다. (HashSet) equals는 (r1, c1) <-> (r2, c2) 교환시에도 같도록 했다.
  • 통과하였고 빠른 속도를 보였다.
  • hashSet은 hashCode로 비교하여 같으면 equals로 비교한다.

구현코드

import java.util.*;

class Solution {
    class Node {
        int r1, c1, r2, c2;
        
        Node(int r1, int c1, int r2, int c2){
            this.r1 = r1;
            this.c1 = c1;
            this.r2 = r2;
            this.c2 = c2;
        }

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getEnclosingInstance().hashCode();
			result = prime * result + c1;
			result = prime * result + c2;
			result = prime * result + r1;
			result = prime * result + r2;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			Node node = (Node)obj;
			if(this.r1 == node.r1 && this.c1 == node.c1 && this.r2 == node.r2 && this.c2 == node.c2) return true;
			if(this.r1 == node.r2 && this.c1 == node.c2 && this.r2 == node.r1 && this.c2 == node.c1) return true;
			return false;
		}

		private Solution getEnclosingInstance() {
			return Solution.this;
		}
        
        
    }
    
    HashSet<Node> visited;
    Queue<Node> q;
    int[][] map;
    int N, answer;
    
    public int solution(int[][] board) {
        answer = 0;
        N = board.length;
        visited = new HashSet<>();
        q = new LinkedList<>();
        map = new int[N + 2][N + 2];
        
        for(int r = 0 ; r < map.length ; ++r){
            for(int c = 0 ; c < map.length ; ++c){
                if(r == 0 || r == map.length - 1 || c == 0 || c == map.length - 1) map[r][c] = 1;
                else map[r][c] = board[r - 1][c - 1];
            }
        }
        
        push(1, 1, 1, 2);
        bfs();
        
        return answer;
    }
    
    private void bfs() {
    	int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    	int[] rotate = {-1, 1};
    	
    	while(!q.isEmpty()) {
    		int size = q.size();
    		
    		for(int i = 0 ; i < size ; ++i) {
    			Node now = q.poll();
    			
    			if((now.r1 == N && now.c1 == N) || (now.r2 == N && now.c2 == N)) return;
    			
    			// 회전 없이 상하좌우 이동 
    			for(int d = 0 ; d < 4 ; ++d) {
    				int nr1 = now.r1 + dir[d][0];
    				int nc1 = now.c1 + dir[d][1];
    				int nr2 = now.r2 + dir[d][0];
    				int nc2 = now.c2 + dir[d][1];
    				
    				if(map[nr1][nc1] == 0 && map[nr2][nc2] == 0) {
    					push(nr1, nc1, nr2, nc2);
    				}
    			}
    			
    			// 가로 회전
    			if(now.r1 == now.r2) {
    				for(int r : rotate) {
    					int nr1 = now.r1 + r;
    					int nc1 = now.c1;
    					int nr2 = now.r2 + r;
    					int nc2 = now.c2;
    					
    					if(map[nr1][nc1] == 0 && map[nr2][nc2] == 0) {
    						push(now.r1, now.c1, nr1, nc1);
    						push(now.r2, now.c2, nr2, nc2);
    					}
    				}
    			}
    			
    			// 세로 회전 
    			if(now.c1 == now.c2) {
    				for(int r : rotate) {
    					int nr1 = now.r1;
    					int nc1 = now.c1 + r;
    					int nr2 = now.r2;
    					int nc2 = now.c2 + r;
    					
    					if(map[nr1][nc1] == 0 && map[nr2][nc2] == 0) {
    						push(now.r1, now.c1, nr1, nc1);
    						push(now.r2, now.c2, nr2, nc2);
    					}
    				}
    			}
    		}
    		answer++;
    	}
    }
    
    private boolean push(int r1, int c1, int r2, int c2) {
    	Node node = new Node(r1, c1, r2, c2);
    	
    	if(visited.contains(node)) return false;
    	
    	visited.add(node);
    	q.offer(new Node(r1, c1, r2, c2));
    	
    	return true;
    }
}