[프로그래머스] [PCCP 기출문제] 4번 / 수레 움직이기 - Java

문제

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

프로그래머스

 

---

문제 개요

이 문제는 n x m 크기의 격자 모양 퍼즐판에서 두 개의 수레(빨간색과 파란색)를 각각 자신의 도착 칸으로 이동시키는 퍼즐을 푸는 문제입니다. 수레들은 상하좌우로 한 칸씩 이동하며, 여러 제약 조건을 준수해야 합니다.

• 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
• 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
• 자신의 도착 칸에 위치한 수레는 움직이지 않습니다.
• 계속 해당 칸에 고정해 놓아야 합니다. 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
• 수레끼리 자리를 바꾸며 움직일 수 없습니다.

접근 방법

1. 초기 상태 설정
   • 퍼즐판(maze)를 순회하여 빨간 수레의 시작 위치(curRed)와 파란 수레의 시작 위치(curBlue)를 찾습니다.
   • 각 수레의 방문 여부를 표시하기 위한 3차원 배열 v를 선언합니다.
     • v[i][j][0]: 빨간 수레가 (i, j)를 방문했는지.
     • v[i][j][1]: 파란 수레가 (i, j)를 방문했는지.
   • min: 최소 턴 수를 추적하기 위한 변수. 초기값은 Integer.MAX_VALUE로 설정합니다.
2. 백트래킹 함수 정의
   • bt(maze, cnt, curRed, curBlue):
     • cnt: 현재까지 소모된 턴 수.
     • curRed, curBlue: 현재 빨간/파란 수레의 위치.
   • 종료 조건:
     • 빨간 수레와 파란 수레가 모두 목표 지점에 도달했을 경우 min 값을 업데이트하고 종료합니다.
   • 다음 상태 탐색:
     • 두 수레가 상하좌우로 이동 가능한 모든 조합을 탐색합니다.
     • 각 이동이 유효한지 판단하기 위해 isPossible 함수를 호출합니다.
     • 이동 후, 현재 이동을 기록하고 다음 턴으로 재귀 호출합니다.
     • 재귀 호출이 끝나면 이동 기록을 복구하고 탐색을 계속 진행합니다.
3. 이동 가능 여부 판단 함수
   • isPossible(maze, curRed, curBlue, red, blue):
     • 다음 조건을 확인하여 두 수레가 주어진 위치로 이동 가능한지 판단합니다.
       • 퍼즐판 경계 확인: 다음 위치가 퍼즐판 바깥인지.
       • 방문 여부: 아직 방문하지 않은 위치인지.
       • 벽 확인: 이동하려는 칸이 벽인지.
       • 수레 간 충돌 확인: 두 수레가 동일한 칸으로 이동하거나 서로 자리를 바꾸는지.
   • 위 조건 중 하나라도 만족하지 않으면 false를 반환합니다.

고려사항

1. 수레 간 충돌 규칙 처리
   두 수레가 같은 칸으로 이동하거나, 서로 자리를 바꾸는 상황은 반드시 방지해야 합니다.
2. 도착 후 움직임 제한
   목표 지점에 도달한 수레는 이후 움직임에서 제외하고 고정해 둡니다.
3. 백트래킹 최적화
   이미 방문한 상태를 재탐색하지 않도록 방문 기록(v)을 효과적으로 관리합니다.
4. 퍼즐을 풀 수 없는 경우 처리
   모든 가능한 이동을 탐색했음에도 목표에 도달하지 못한 경우, 0을 반환합니다.

코드

import java.util.*;
class Solution {
    static int min = Integer.MAX_VALUE;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    static boolean[][][] v;  //0=red, 1=blue
    static boolean finishedRed = false;
    static boolean finishedBlue = false;
    
    public int solution(int[][] maze) {
        int answer = 0;
        v = new boolean[maze.length][maze[0].length][2];
        
        Pos curRed = null, curBlue = null;
        for(int i=0; i<maze.length; i++) {
            for(int j=0; j<maze[0].length; j++) {
                if(maze[i][j] == 1) curRed = new Pos(i,j);
                if(maze[i][j] == 2) curBlue = new Pos(i,j);
            }
        }
        v[curRed.r][curRed.c][0] = true;
        v[curBlue.r][curBlue.c][1] = true;
        bt(maze, 0, curRed, curBlue);
        answer = min == Integer.MAX_VALUE ? 0 : min;
        return answer;
    }
    
    public void bt(int[][] maze, int cnt, Pos curRed, Pos curBlue) {
        if(finishedRed && finishedBlue) {
            min = Math.min(cnt, min);
            return;
        }
        
        for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                Pos red = finishedRed ? curRed : new Pos(curRed.r + dr[i], curRed.c + dc[i]);
                Pos blue = finishedBlue ? curBlue : new Pos(curBlue.r + dr[j], curBlue.c + dc[j]);
                
                if(isPossible(maze, curRed, curBlue, red, blue)) {                    
                    v[red.r][red.c][0] = true;
                    v[blue.r][blue.c][1] = true;
                    if(maze[red.r][red.c] == 3) finishedRed = true;
                    if(maze[blue.r][blue.c] == 4) finishedBlue = true;
                    
                    bt(maze, cnt+1, red, blue);
                    
                    v[red.r][red.c][0] = false;
                    v[blue.r][blue.c][1] = false;
                    finishedRed = false;
                    finishedBlue = false;
                }
            }
        }
    }
    
    public boolean isPossible(int[][] maze, Pos curRed, Pos curBlue, Pos red, Pos blue) {
        //판 밖으로 움직일 때
        if(red.r<0 || red.c<0 || red.r>=maze.length || red.c>=maze[0].length) return false;
        if(blue.r<0 || blue.c<0 || blue.r>=maze.length || blue.c>=maze[0].length) return false;
        
        //도착하지 않았으면서 이미 방문했을 때
        if(!finishedRed && v[red.r][red.c][0]) return false;
        if(!finishedBlue && v[blue.r][blue.c][1]) return false;
        
        //움직인 칸이 벽일 때
        if(maze[red.r][red.c] == 5) return false;
        if(maze[blue.r][blue.c] == 5) return false;
        
        //수레끼리 자리를 바꿨을 때
        if((red.r == curBlue.r && red.c == curBlue.c) && (blue.r == curRed.r && blue.c == curRed.c)) return false;
        
        //같은 자리일 때
        if(red.r == blue.r && red.c == blue.c) return false;
        
        return true;
    }
    
    static class Pos{
        int r, c;
        public Pos(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}