프로그래머스

 

핵심

- 노드의 좌표가 2개라는 점.

- 노드의 상태도 있다는 점.. (두 점이, 가로일 때, 세로일 때) -> 신유형

- 상태에 마다, 방향 로직도 다르다는 점.

 

 

소스코드

단계 1. 노드 정의. 상태를 고려하여 노드 정의
단계 2. 초기 설정. 초기값 큐에 넣기. 루트노드이다. 처음 탐색할 떄, 반드시 있어야함.
단계 3. 탐색 시작. 큐가 빌때까지 무한반복 (BFS)
단계 4. 검사 단계. 노드 검사하기. 이상한 노드, 요구사항 로직에 벗어나는 노드 검사 or 재방문 허용하는지   <- 검사 로직
단계 5. 종료 조건 설정. 종료 조건을 설정한다. < 종료 로직
단계 6. 노드 재방문 설정. 방문 배열에 체크 <- visited 배열 로직
단계 7. 방향 큐잉. 모든 방향 다 넣기 <- 큐잉 로직

class Solution {
	// 단계 1. 노드 정의. 상태를 고려하여 노드 정의
    class Item{
        int x1, x2, y1, y2, time, vertical;
        Item(int x1, int y1, int x2, int y2, int time, int v){
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.time = time;
            this.vertical = v;
        }
    }
    
    public int solution(int[][] board) {
        int answer = 0;
        Queue<Item> q = new LinkedList<>();
        int[][] op = {{1,0},{-1,0},{0,1},{0,-1}};
        boolean[][][] visited = new boolean[board.length][board.length][2];
        
        // 단계 2. 초기 설정. 초기값 큐에 넣기. 루트노드이다. 처음 탐색할 떄, 반드시 있어야함.
        q.offer(new Item(0, 0, 0, 1, 0, 0));
        
        // 단계 3. 탐색 시작. 큐가 빌때까지 무한반복 (BFS)
        while(!q.isEmpty()){
            Item item = q.peek();
            q.poll();
            
            // 단계 4. 검사 단계. 노드 검사하기. 이상한 노드, 요구사항 로직에 벗어나는 노드 검사.   <- 검사 로직
            if(item.x1 < 0 || item.x1 >= board.length || item.y1 < 0 || item.y1 >= board.length ||
                   item.x2 < 0 || item.x2 >= board.length || item.y2 < 0 || item.y2 >= board.length){
                continue;
            }
            
            if(board[item.x1][item.y1] == 1 || board[item.x2][item.y2] == 1){
                continue;
            }
            
            if(visited[item.x1][item.y1][item.vertical] && 
              visited[item.x2][item.y2][item.vertical])
                continue;
                
            // 단계 5. 종료 조건 설정. 종료 조건을 설정한다. < 종료 로직
            if((item.x1 == board.length - 1 && item.y1 == board.length - 1) ||
               (item.x2 == board.length - 1 && item.y2 == board.length - 1)){
                answer = item.time;
                break;
            }
            
            // 단계 6. 노드 재방문 설정. 방문 배열에 체크 <- visited 배열 로직
            visited[item.x1][item.y1][item.vertical] = true;
            visited[item.x2][item.y2][item.vertical] = true;
            
            // 단계 7. 방향 큐잉. 모든 방향 다 넣기 <- 큐잉 로직
            for(int i = 0; i < op.length; i++){
                int n_x1 = item.x1 + op[i][0];
                int n_y1 = item.y1 + op[i][1];
                int n_x2 = item.x2 + op[i][0];
                int n_y2 = item.y2 + op[i][1];
 
                q.offer(new Item(n_x1, n_y1, n_x2, n_y2, item.time + 1, item.vertical));
            }
            
            if (item.vertical == 1) {
                if(item.y1 - 1 >= 0 && board[item.x1][item.y1 - 1] == 0 && board[item.x2][item.y2 - 1] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1, item.y1 - 1, item.time + 1, 0));
                    q.offer(new Item(item.x2, item.y2, item.x2, item.y2 - 1, item.time + 1, 0));
                }
                
                if(item.y1 + 1 <= (board.length - 1) && 
                   board[item.x1][item.y1 + 1] == 0 && board[item.x2][item.y2 + 1] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1, item.y1 + 1, item.time + 1, 0));
                    q.offer(new Item(item.x2, item.y2, item.x2, item.y2 + 1, item.time + 1, 0));                    
                }
            }
            else {
                if(item.x1 - 1 >= 0 && board[item.x1 - 1][item.y1] == 0 &&
                  board[item.x2 - 1][item.y2] == 0){            
                    q.offer(new Item(item.x1, item.y1, item.x1 - 1, item.y1, item.time + 1, 1));
                    q.offer(new Item(item.x2, item.y2, item.x2 - 1, item.y2, item.time + 1, 1));
                }
                
                if(item.x1 + 1 <= (board.length - 1) && board[item.x1 + 1][item.y1] == 0 &&
                  board[item.x2 + 1][item.y2] == 0){
                    q.offer(new Item(item.x1, item.y1, item.x1 + 1, item.y1, item.time + 1, 1));
                    q.offer(new Item(item.x2, item.y2, item.x2 + 1, item.y2, item.time + 1, 1));    
                }
            }
        }
 
        return answer;
    }
}