haleylog

요구사항

주어진 퍼즐판에서 빨간색과 파란색 수레가 각각의 주어진 도착 칸으로 이동해야 할때

1. 각 수레는 벽이나 격자 밖으로 나갈 수 없다.

2. 동시에 두 수레가 같은 칸에 있을 수 없다.

3. 수레는 상하좌우로만 움직일 수 있다.

4. 도착지에 도착하기 전까지 각 턴마다 수레를 무조건 움직여야 한다.

5. 두 수레가 서로 위치를 바꿀수 없다.

위와 같은 조건으로 가는 경로의 경우의 수 중에 최소값 구하기.

입력 값

풀이

1. 각 수레의 출발 칸과 도착 칸의 좌표 구하기

    -> 출발 칸 방문 여부 수레 별 각각 저장

2. 상하좌우 이동 가능한 모든 경우의 수 구하기 (Backtracking)

    -> 상하좌우 칸 중 퍼즐 판 내에서 벽인 경우 Pass

    -> 상하좌우 칸 중 각 수레가 방문한 적 있는 경우 Pass

    -> 상하좌우 칸 중 두 수레가 동일한 칸으로 이동하는 경우 Pass

    -> 상하좌우 칸 중 수레간 상호 교환하는 이동인 경우 Pass

    -> 이동 경로 저장 후 이동횟수 + 1 처리 하여 다음 이동 경로 추가 탐색 반복 (재귀)

3. 빨간 수레와 파란 수레가 각각 도착 좌표에 도착하면 총 이동 횟수 Min 비교

    -> 퍼즐은 최대 4*4 크기이므로 최초 minCount 는 16으로 시작 (16회 이상 움직일 수 없음)

4. 최소 이동 횟수 return

    -> minCount가 16 인 경우 한번도 도착하지 못했으므로 0 return

Java 코드

import java.util.*;

class Solution {
    // 수레 별 이동 경로
    static boolean[][] rMove, bMove;
    static int minCount = 16;
    
    public int solution(int[][] maze) {
        int answer = 0;
        
        rMove = new boolean[maze.length][maze[0].length];
        bMove = new boolean[maze.length][maze[0].length];
        
        // 수레 별 현재/끝 좌표
        int[] red       = new int[2];
        int[] redGoal   = new int[2];
        int[] blue      = new int[2];
        int[] blueGoal  = new int[2];
        
        // 시작 칸과 끝 칸 먼저 구하기
        for(int i=0; i<maze.length;i++) {
            for(int j=0; j<maze[0].length;j++) {
                if(maze[i][j] == 1) { red       = new int[]{i, j}; rMove[i][j] = true;}
                if(maze[i][j] == 2) { blue      = new int[]{i, j}; bMove[i][j] = true;}
                if(maze[i][j] == 3) { redGoal   = new int[]{i, j}; }
                if(maze[i][j] == 4) { blueGoal  = new int[]{i, j}; }
            }
        }
        
        move(red, blue, redGoal, blueGoal, maze, 0);
        answer = minCount == 16 ? 0 : minCount;
         
        return answer;
    }
    
    private void move(int[] red, int[] blue, int[] redGoal, int[] blueGoal, int[][] maze, int moveCnt) {
        int redX    = red[1];
        int redY    = red[0];
        int blueX   = blue[1];
        int blueY   = blue[0];
        
        if(redX == redGoal[1] && redY == redGoal[0] && blueX == blueGoal[1] && blueY == blueGoal[0]) {
            minCount = Math.min(minCount, moveCnt);
            return;
        }
        
        // 상하좌우 탐색용
        int[] rx    = {0, 0, -1, 1};
        int[] ry    = {-1, 1, 0, 0};
        int maxX    = maze[0].length;
        int maxY    = maze.length;
        
        List<int[]> redDirections   = new ArrayList<>();
        List<int[]> blueDirections  = new ArrayList<>();

        if(redX == redGoal[1] && redY == redGoal[0]) redDirections.add(red);
        else {
            for(int i=0; i<4; i++) {
                if(redX + rx[i] < 0 || redX + rx[i] >= maxX || redY + ry[i] < 0 || redY + ry[i] >= maxY
                  || rMove[redY + ry[i]][redX + rx[i]]
                  || maze[redY + ry[i]][redX + rx[i]] == 5
                  ) continue;

                redDirections.add(new int[]{redY + ry[i], redX + rx[i]});
            }
        }

        if(blueX == blueGoal[1] && blueY == blueGoal[0]) blueDirections.add(blue);
        else {
            for(int i=0; i<4; i++) {
                if(blueX + rx[i] < 0 || blueX + rx[i] >= maxX || blueY + ry[i] < 0 || blueY + ry[i] >= maxY
                  || bMove[blueY + ry[i]][blueX + rx[i]]
                  || maze[blueY + ry[i]][blueX + rx[i]] == 5
                  ) continue;

                blueDirections.add(new int[]{blueY + ry[i], blueX + rx[i]});
            }
        }

        for(int[] rDirection : redDirections) {
            for(int[] bDirection : blueDirections) {
                // 동일한 장소로 이동하는 경우 Pass
                if(rDirection[0] == bDirection[0] && rDirection[1] == bDirection[1]) continue;
                // 서로 자리 바꾸는 경우 Pass
                if(rDirection[0] == blueY && rDirection[1] == blueX
                  && bDirection[0] == redY && bDirection[1] == redX) continue;

                rMove[rDirection[0]][rDirection[1]] = true;
                bMove[bDirection[0]][bDirection[1]] = true;

                move(rDirection, bDirection, redGoal, blueGoal, maze, moveCnt+1);
                
                rMove[rDirection[0]][rDirection[1]] = false;
                bMove[bDirection[0]][bDirection[1]] = false;
            }
        }
    }
    
}

문제 출처

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