프로그래머스 수레 움직이기 (java)

한강섭·2025년 6월 25일

알고리즘 프로그래머스

알고리즘 문제 풀이

목록 보기

18/26

[PCCP 기출문제] 4번 / 수레 움직이기

관찰

수레를 옮길 때 두 수레를 1 카운트 하면서 dfs를 통해 옮기는 방식을 선택하였다.

왜 이 방식을 선택했냐면 "동시에 두 수레를 같은 칸으로 움직일 수 없습니다." 이 조건에 대해 어떤 수레를 먼저 움직이는지에 따라 결과가 달라지기 때문에 완전탐색을 위해 dfs를 선택하였다.

그리고 종료 조건을 둘 다 목적지에 도착했을 때 종료시켜주면서 모든 경우의 수 중 최소값을 탐색한다 (칸이 4*4라서 충분히 가능할 듯)

정답 코드

import java.io.*;
import java.util.*;

class Solution {
    static int n,m,min;
    static int[][] visitedA, visitedB;
    static int[] sA,eA,sB,eB;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    
    public int solution(int[][] maze) {
        int answer = 0;
        n = maze.length;
        m = maze[0].length;
        
        visitedA = new int[n][m];
        visitedB = new int[n][m];
        
        sA = new int[2];
        eA = new int[2];
        sB = new int[2];
        eB = new int[2];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maze[i][j] == 1){
                    sA[0] =i; sA[1] = j;
                    visitedA[i][j] = 1;
                }
                if(maze[i][j] == 2){
                    sB[0] =i; sB[1] = j;
                    visitedB[i][j] = 1;
                }
                if(maze[i][j] == 3){
                    eA[0] =i; eA[1] = j;
                }
                if(maze[i][j] == 4){
                    eB[0] =i; eB[1] = j;
                }
            }
        }
        
        min = Integer.MAX_VALUE;
        
        dfs(sA,sB,maze,0,visitedA,visitedB);
        
        if(min == Integer.MAX_VALUE) answer = 0;
        else answer = min;
        
        return answer;
    }
    
    public void dfs(int[] startA, int[] startB, int[][] map, int count, int[][] vA, int[][] vB){
        // System.out.println(startA[0] + " " + startA[1] + " || " + startB[0] + " " + startB[1] + " ||  count = " + count);

        if(startA[0] == eA[0] && startA[1] == eA[1] && startB[0] == eB[0] && startB[1] == eB[1]){
            if(min > count) min = count;
            return;
        }
        
        // 빨간 수레 가능한 이동 위치
        ArrayList<int[]> aList = new ArrayList<>();
        // 빨간 수레가 도착하지 않은 경우에만 이동 가능
        if(!(startA[0] == eA[0] && startA[1] == eA[1])) {
            for(int i=0;i<4;i++){
                int[] addA = new int[2];
                int nr = startA[0] + dr[i];
                int nc = startA[1] + dc[i];
                if(nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
                if(vA[nr][nc] == 1) continue;
                if(map[nr][nc] == 5) continue;
                addA[0] = nr;
                addA[1] = nc;
                aList.add(addA);
            }
        } else {
            // 빨간 수레가 도착한 경우 현재 위치 유지
            aList.add(new int[]{startA[0], startA[1]});
        }
        
        // 파란 수레 가능한 이동 위치
        ArrayList<int[]> bList = new ArrayList<>();
        // 파란 수레가 도착하지 않은 경우에만 이동 가능
        if(!(startB[0] == eB[0] && startB[1] == eB[1])) {
            for(int i=0;i<4;i++){
                int[] addB = new int[2];
                int nr = startB[0] + dr[i];
                int nc = startB[1] + dc[i];
                if(nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
                if(vB[nr][nc] == 1) continue;
                if(map[nr][nc] == 5) continue;
                addB[0] = nr;
                addB[1] = nc;
                bList.add(addB);
            }
        } else {
            // 파란 수레가 도착한 경우 현재 위치 유지
            bList.add(new int[]{startB[0], startB[1]});
        }
        
        // 모든 이동 조합 시도
        for(int[] tmpA : aList){
            for(int[] tmpB : bList){
                // 같은 칸으로 이동 방지
                if(tmpA[0] == tmpB[0] && tmpA[1] == tmpB[1]) continue;
                
                // 자리 바꾸기 방지
                if(startA[0] == tmpB[0] && startA[1] == tmpB[1] &&
                   startB[0] == tmpA[0] && startB[1] == tmpA[1]) continue;
                
                // 방문 배열 복사 및 업데이트
                int[][] newVA = new int[n][m];
                int[][] newVB = new int[n][m];
                for (int i = 0; i < n; i++) {
                    newVA[i] = Arrays.copyOf(vA[i], m);
                    newVB[i] = Arrays.copyOf(vB[i], m);
                }
                
                // 실제로 이동한 경우에만 방문 표시
                if(!(startA[0] == eA[0] && startA[1] == eA[1])) {
                    newVA[tmpA[0]][tmpA[1]] = 1;
                }
                if(!(startB[0] == eB[0] && startB[1] == eB[1])) {
                    newVB[tmpB[0]][tmpB[1]] = 1;
                }
                
                dfs(tmpA, tmpB, map, count+1, newVA, newVB);
            }
        }
    }
    
}

풀이

두 수레가 이동할 수 있는 경로를 모두 파악

빨간 수레가 가능한 이동 위치를 aList에 담고, 파란 수레가 가능한 이동 위치를 bList에 담는다. 그 후에 모든 이동 조합을 한 후 같은 칸으로 이동을 막아주고, 자리 바꾸기를 통한 이동을 막아준다 ~~(이거를 처음에 안해서 계속 81점 나옴..)~~ 그렇게 되면 가능한 둘 수 있는 방법을 모두 두고 count+1 하면서 모든 경로를 파악할 수 있다.

시행착오

백트래킹 문제

int[][] newVA = new int[n][m];
int[][] newVB = new int[n][m];
for (int i = 0; i < n; i++) {
    newVA[i] = Arrays.copyOf(vA[i], m);
    newVB[i] = Arrays.copyOf(vB[i], m);
}

dfs(tmpA, tmpB, map, count+1, newVA, newVB);