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

1. 문제

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

2. 풀이

참고 풀이
https://github.com/ndb796/python-for-coding-test/blob/master/13/8.java

최단 거리이기때문에 BFS로 푸는 것이 맞다.

2-1. ✨핵심 Point

1. 범위체크를 하기 귀찮기 때문에 주어진 board 주변을 1(벽)로 다 채운다.
   ex)
   1 1 1 1 1
   1 0 0 1 1
   1 1 0 1 1
   1 1 1 1 1

2. 두 칸을 대상으로 방문체크를 진행해주면 된다.
   방문한 Node를 담는 ArrayList visited = new ArrayList<>();

• 해당 노드가 갈 수 있는 점들을 함수 getNextPos로 구한다.
• getNextPos로 구한 점들이 visited에 있는지 체크한다.

3. getNextPos

• 일단 4방향으로 이동.
• 가로로 놓여있을 경우, 세로로 놓여있을 경우 나눠서 구하기.

  1. 로봇이 가로로 놓인 상태에서 아래쪽으로 회전하는 경우
  2. 로봇이 가로로 놓인 상태에서 위쪽으로 회전하는 경우
  3. 로봇이 세로로 놓인 상태에서 오른쪽으로 회전하는 경우
  4. 로봇이 세로로 놓인 상태에서 왼쪽으로 회전하는 경우

3. 코드

import java.util.*;

class Solution {
    public class Node{
        int x1;
        int y1;
        int x2;
        int y2;
        int distance;
        
        public Node(int x1, int y1, int x2, int y2, int distance){
            this.x1 = x1;
            this.x2 = x2;
            this.y1 = y1;
            this.y2 = y2;
            this.distance = distance;
        }
    }
    public int solution(int[][] board) {
        int n = board.length;
        int[][] newBoard = new int[n+2][n+2];
        for(int i = 0; i < n+2; i++){
            for(int j = 0; j < n+2; j++){
                newBoard[i][j] = 1;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                newBoard[i+1][j+1] = board[i][j];
            }
        }
        
        Queue<Node> q = new LinkedList<>();
        ArrayList<Node> visited = new ArrayList<>();
        
        
        q.add(new Node(1, 1, 1, 2, 0));
        visited.add(new Node(1, 1, 1, 2, 0));
        
        while(!q.isEmpty()){
            Node node = q.poll();
            
            if( (node.x1 == n && node.y1 == n) || (node.x2 == n && node.y2 == n)){
                return node.distance;
            }
            
            ArrayList<Node> nextPos = getNextPos(node, newBoard);
            for(int i = 0; i < nextPos.size(); i++){
                Node nextNode = nextPos.get(i);
                boolean check = true;
                
                // if(visited.contains(nextNode)){
                //     check = false;
                // }
                for(int j = 0; j < visited.size(); j++){
                    Node visitedNode = visited.get(j);
                    if(nextNode.x1 == visitedNode.x1 && nextNode.y1 == visitedNode.y1 && nextNode.x2 == visitedNode.x2 && nextNode.y2 == visitedNode.y2){   
                        check = false;
                        break;
                    }
                }
                
                if(check){
                    q.add(nextNode);
                    visited.add(nextNode);
                }
            }
        }
        return 0;
    }
    
    public ArrayList<Node> getNextPos(Node node, int[][] board){
        int[] moveX = {1, -1, 0, 0};
        int[] moveY = {0, 0, 1, -1};
        ArrayList<Node> nextPos = new ArrayList<>();
        
        for(int i = 0; i < 4; i++){
            int goX1 = node.x1 + moveX[i];
            int goY1 = node.y1 + moveY[i];
            int goX2 = node.x2 + moveX[i];
            int goY2 = node.y2 + moveY[i];
            
            if(board[goX1][goY1] == 0 && board[goX2][goY2] == 0){
                nextPos.add(new Node(goX1, goY1, goX2, goY2, node.distance + 1));    
            }
        }
        
        // 가로로 놓여있을경우
        int[] hor = {-1, 1};
        if(node.x1 == node.x2){
			for(int i = 0; i < 2; i++) {
				if( board[node.x1 + hor[i]][node.y1] == 0 && board[node.x2 + hor[i]][node.y2] == 0 ) {
                    nextPos.add(new Node(node.x1, node.y1, node.x1 + hor[i], node.y1, node.distance+1));
                    nextPos.add(new Node(node.x2, node.y2, node.x2 + hor[i], node.y2, node.distance+1));
				}
			}
        }
        
        //세로로 놓여있는경우
        int[] ver = {-1, 1};
        if(node.y1 == node.y2){
            for(int i = 0; i < 2; i++) {
				if(board[node.x1][node.y1 + ver[i]] == 0 && board[node.x2][node.y2 + ver[i]] == 0) {
                    nextPos.add(new Node(node.x1, node.y1, node.x1, node.y1 + ver[i], node.distance+1));
                    nextPos.add(new Node(node.x2, node.y2, node.x2, node.y2 + ver[i], node.distance+1));
				}
			}
        }
        return nextPos;
    }
}