프로그래머스 수레 움직이기 자바 풀이

문제 링크

문제 풀이 시간 :

문제 요약

n x m 격자에 빨간 수레와 파란 수레가 각자의 도착 칸까지 이동해야 함
매 턴마다 두 수레를 모두 상하좌우로 한 칸씩 움직여야 하고, 벽·자신이 방문했던 칸으로는 이동 불가
도착한 수레는 그 칸에 고정, 두 수레가 같은 칸으로 이동하거나 자리를 맞바꾸는 것도 불가
격자 크기는 최대 4 x 4이고, 풀 수 없으면 0을 반환

문제 풀이

처음엔 BFS로 두 수레의 위치 쌍을 상태로 두고 방문 배열을 관리하면서 최소 턴을 구하면 되겠다고 생각했다.

하지만 "지나온 칸을 다시 밟을 수 없다"는 조건 때문에 상태를 그냥 (빨간 수레 위치, 파란 수레 위치)만으로 정의할 수 없다.

같은 위치에 있어도 지금까지 지나온 경로가 다르면 다음에 갈 수 있는 칸이 달라지기 때문에, 위치만 갖고 BFS 방문 처리를 하면 실제로는 갈 수 있는 경로인데 이미 방문한 상태로 착각해 걸러버릴 수 있다.

이 문제의 핵심은 격자 크기가 최대 4x4로 아주 작으니, 지나온 칸을 방문 배열에 표시했다가 되돌리는 백트래킹 DFS로 완전탐색해도 시간 안에 끝난다는 점이다.

대신 지금까지 찾은 최소 턴(answer)보다 이미 턴 수가 많아지면 그 가지를 그대로 잘라내는 가지치기를 더해서 탐색량을 줄인다.

두 수레를 동시에 한 칸씩 옮기며 재귀 호출한다.
이미 도착 칸에 있는 수레는 고정하고, 나머지 수레만 상하좌우로 움직인다.
두 수레가 같은 칸으로 이동하거나 서로 자리를 맞바꾸는 이동은 후보에서 제외한다.
두 수레가 모두 도착 칸에 있으면 지금까지의 턴 수와 answer를 비교해 갱신한다.

최종 코드

java

class Solution {
    public int answer = Integer.MAX_VALUE;
    public int[][] maze, dir = {{0,1},{0,-1},{1,0},{-1,0}};
    public boolean[][][] visited;
    public int n, m;
    
    public void dfs(int cnt, int rx, int ry, int bx, int by){
        if(cnt>=answer)
            return;
        
        if(maze[rx][ry] == 3 && maze[bx][by] == 4){
            answer = Math.min(answer, cnt);
            return;
        }
        
        for(int r=0;r<(maze[rx][ry] == 3? 1 : 4);r++){
            int nrx = rx;
            int nry = ry;
            
            boolean redFlag = maze[rx][ry] != 3;
            
            if(redFlag){
                nrx = rx + dir[r][0];
                nry = ry + dir[r][1];
                
                if(nrx < 0 || nrx >= n || nry <0 || nry >= m || maze[nrx][nry] == 5 || visited[0][nrx][nry])
                    continue;
                
                visited[0][nrx][nry] = true;
            }
            
            for(int b=0;b<(maze[bx][by] == 4 ? 1 : 4);b++){
                int nbx = bx;
                int nby = by;
                
                boolean blueFlag = maze[bx][by] != 4;
                
                if(blueFlag){
                    nbx = bx + dir[b][0];
                    nby = by + dir[b][1];
                    
                    if(nbx < 0 || nbx >=n || nby < 0 || nby >=m || maze[nbx][nby] == 5 || visited[1][nbx][nby])
                        continue;
                }
                if(nrx == nbx && nry == nby)
                        continue;
                    
                if (nrx == bx && nry == by &&
                    nbx == rx && nby == ry) {
                    continue;
                }
                    
                if (blueFlag)
                    visited[1][nbx][nby] = true;
                
                dfs(cnt + 1, nrx, nry, nbx, nby);
                
                if (blueFlag)
                    visited[1][nbx][nby] = false;
            }
            if(redFlag)    
                visited[0][nrx][nry] = false;
        }
    }
    
    public int solution(int[][] maze) {
        n = maze.length;
        m = maze[0].length;
        this.maze = maze;
        
        visited = new boolean[2][n][m];
        
        int rx=0, ry=0, bx=0, by=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(maze[i][j]==1){
                    rx = i;
                    ry = j;
                }
                if(maze[i][j]==2){
                    bx = i;
                    by = j;
                }
            }
        }
        visited[0][rx][ry] = true;
        visited[1][bx][by] = true;
        
        dfs(0, rx, ry, bx, by);
        
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
}

수레 움직이기

문제 풀이 시간 :

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기