Lv.3 [PCCP 기출문제] 4번 / 수레 움직이기 [JAVA]

문제링크

성공 여부(걸린 시간): 성공(1시간 20분 21초)

아이디어

두 수레(빨간/파란)를 동시에 이동시키며 각각 도착지에 도달하는 데 필요한 최소 이동 횟수를 구해야 한다.
두 수레는 다음 조건들을 만족하며 이동해야 한다.

1. 서로 같은 칸을 동시에 점유할 수 없음
2. 서로 자리를 교차해 지나갈 수 없음
3. 도착지에 도착한 수레는 더 움직이지 않음
4. 각 수레는 이미 자신이 이동했던 칸을 다시 방문할 수 없음
5. 벽(5)은 이동 불가

• BFS 사용
• 상태는
  {R_x, R_y, B_x, B_y, 이동 횟수}
• 각 상태에서 양쪽 수레가 독립적으로 상하좌우 움직임
  → 최대 16가지 경우 탐색
• 방문 체크는 boolean[N][M][2] 형태로
  각 수레가 방문한 칸을 저장
• 단, 두 수레의 동시 이동 + 교차 불가 등 제약 때문에
  visited 배열을 deep copy하여 상태마다 별도로 관리
• 두 수레 모두 도착지에 도달 시 answer 갱신

---

코드

import java.util.*;

class Solution {
    static int N, M;
    static class Node{
        int [] loc;
        boolean [][][] visited;
        public Node(int [] loc, boolean [][][] visited){
            this.loc = loc;
            this.visited = visited;
        }
    }
    public int solution(int[][] maze) {
        int answer = Integer.MAX_VALUE;
        N = maze.length;
        M = maze[0].length;
        int [] end = new int [4];
        int [] start = new int [4];
        // 벽과 빈칸 빼고 정보 저장 후 전부 초기화 
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(maze[i][j]==1){
                    start[0] = i;
                    start[1] = j;
                }
                else if(maze[i][j]==2){
                    start[2] = i;
                    start[3] = j;
                }
                else if(maze[i][j]==3){
                    end[0] = i;
                    end[1] = j;
                }
                else if(maze[i][j]==4){
                    end[2] = i;
                    end[3] = j;
                }
                if(maze[i][j]!=5){
                    maze[i][j] =0;
                }
            }
        }
        //BFS를 돌면서 이동

        ArrayDeque<Node> q = new ArrayDeque<>();
        boolean [][][] arr = new boolean[N][M][2];
        arr[start[0]][start[1]][0] = true;
        arr[start[2]][start[3]][1] = true;

        q.add(new Node(new int[]{start[0], start[1], start[2],start[3], 0},arr ));
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        while(!q.isEmpty()){
            Node now = q.poll();
            int [] cur = now.loc;
            int nowRX = cur[0];
            int nowRY = cur[1];
            int nowBX = cur[2];
            int nowBY = cur[3];
            int cnt = cur[4];
            if(cnt>answer){
                continue;
            }
            if(nowRX == end[0] && nowRY == end[1] && nowBX == end[2] && nowBY == end[3]){
                answer = Math.min(answer, cnt);
                continue;
            }
            boolean [] isDest = {true, true};
            for(int i=0; i<4; i++){
                int moveRX = nowRX;
                int moveRY = nowRY;
                if(nowRX != end[0] || nowRY != end[1]){
                    moveRX += dx[i];
                    moveRY += dy[i]; 
                    isDest[0] = false;
                }
                for(int j = 0; j<4; j++){
                    int moveBX = nowBX;
                    int moveBY = nowBY;
                    if(nowBX != end[2] || nowBY != end[3]){
                        moveBX += dx[j];
                        moveBY += dy[j];
                        isDest[1] = false; 
                    }
                    // 서로 겹치지않고 이동이 가능하다면
                    if(canGo(moveRX, moveRY)&&canGo(moveBX, moveBY) 
                       && (moveRX!=moveBX ||moveRY!=moveBY) 
                       && ((moveRX!= nowBX || moveRY!= nowBY) || (moveBX!= nowRX || moveBY!=nowRY))
                       && maze[moveRX][moveRY]!=5 && maze[moveBX][moveBY]!=5 ){
                        // 이미 자신의 도착칸에 도착했다면 이동할 수 없기에 visited 검사 X

                        if((!isDest[0] && now.visited[moveRX][moveRY][0])||(!isDest[1] && now.visited[moveBX][moveBY][1])){
                            continue;
                        }
                        boolean [][][] nowVisited = deepCopy(now.visited);
                        nowVisited[moveRX][moveRY][0] = true;
                        nowVisited[moveBX][moveBY][1] = true;
                        q.add(new Node(new int[]{moveRX, moveRY, moveBX, moveBY, cnt+1}, nowVisited));
                    }
                }
            }
        }
        return answer==Integer.MAX_VALUE? 0:answer;
    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<N&&y<M;
    }
    static boolean [][][] deepCopy(boolean [][][] arr){
        boolean [][][] temp = new boolean[N][M][2];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                for(int k=0; k<2; k++){
                    temp[i][j][k] = arr[i][j][k];
                }
            }
        }
        return temp;
    }
}