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

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

참고 블로그 : https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%B8%94%EB%A1%9D-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-Java

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

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

import java.util.*;

class Solution {
    static class Node {
	int x1, x2, y1, y2; // 두 지점에 대한 x좌표, y좌표

	public Node(int x1, int y1, int x2, int y2) {
		this.x1 = x1;
		this.x2 = x2;
		this.y1 = y1;
		this.y2 = y2;
	}
        
        @Override
	public int hashCode() { // hashCode를 설정하고 안하고의 차이가 크다.
		final int prime = 31;
		int result = 1;
		result = prime * result + x1;
		result = prime * result + x2;
		result = prime * result + y1;
		result = prime * result + y2;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		Node node = (Node)obj;
		if(this.x1 == node.x1 && this.y1 == node.y1 && this.x2 == node.x2 && this.y2 == node.y2) return true;
		if(this.x1 == node.x2 && this.y1 == node.y2 && this.x2 == node.x1 && this.y2 == node.y1) return true;
		return false;
	}

}

  static int answer = 0;
  static HashSet<Node> visited = new HashSet<Node>();
  static LinkedList<Node> qu = new LinkedList<Node>();
  static int [][] map;

  public int solution(int[][] board) {
  	map = new int [board.length+2] [board.length+2];
	for (int i = 0; i < map.length; i++) {
		for (int j = 0; j < map.length; j++) {
			if(i == 0 || i == map.length-1 || j == 0 || j == map.length-1) map[i][j] = 1;
			else map[i][j] = board[i-1][j-1];
		}
	}
	push(1, 1, 1, 2);
	bfs();
    	return answer;
    }

  private static void bfs() {
	int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 좌, 우, 아래, 위
    	int[] rotate = {-1, 1}; // 반시계, 시계
    	
    	while(!qu.isEmpty()) {
    		int size = qu.size();
    		for (int i = 0; i < size; i++) {
			Node node = qu.poll();
			if((node.x1 == map.length-2 && node.y1 == map.length-2) || (node.x2 == map.length-2 && node.y2 == map.length-2)) return; // 도착
				// 회전 없이 상하좌우 이동 
    			for(int d = 0 ; d < 4 ; ++d) {
    				int nx1 = node.x1 + dir[d][0];
    				int ny1 = node.y1 + dir[d][1];
    				int nx2 = node.x2 + dir[d][0];
    				int ny2 = node.y2 + dir[d][1];
    				
    				if(map[nx1][ny1] == 0 && map[nx2][ny2] == 0) { // 갈수록 있으면 추가
    					push(nx1, ny1, nx2, ny2);
    				}
    			}
    			// 가로 회전
    			if(node.x1 == node.x2) {
    				for(int r : rotate) {
    					int nx1 = node.x1 + r;
    					int ny1 = node.y1;
    					int nx2 = node.x2 + r;
    					int ny2 = node.y2;
    					
    					if(map[nx1][ny1] == 0 && map[nx2][ny2] == 0) { // 갈수록 있으면 추가
    						push(node.x1, node.y1, nx1, ny1);
    						push(node.x2, node.y2, nx2, ny2);
    					}
    				}
    			}
    			// 세로 회전 
    			if(node.y1 == node.y2) {
    				for(int r : rotate) {
    					int nx1 = node.x1;
    					int ny1 = node.y1 + r;
    					int nx2 = node.x2;
    					int ny2 = node.y2 + r;
    					
    					if(map[nx1][ny1] == 0 && map[nx2][ny2] == 0) { // 갈수록 있으면 추가
    						push(node.x1, node.y1, nx1, ny1);
    						push(node.x2, node.y2, nx2, ny2);
    					}
    				}
    			}
			}
    		answer++;
    	}
	}
private static boolean push(int x1, int y1, int x2, int y2) {
	Node n = new Node(x1, y1, x2, y2);
	if(visited.contains(n)) return false; // 해당 Node가 있으면 취소
    	visited.add(n);
    	qu.offer(new Node(x1, y1, x2, y2));
    	return true;
}
}