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

걸린시간 : 2시간

 

전형적인 백트랙킹 문제 + 엄청난 구현 조건 

 

솔직히 말해서

 

해당 조건을 체크하면서 백트랙킹을 진행하면 쉽게 풀리는 문제다. ( 구현 과정이 개빡 )

 

도착점에 들어온 수레는 해당 칸에 고정해 놓아야 한다는 조건을 망각해서 시간을 1시간이나 더 태워먹게 되었다.

 

<정답 코드>

 

import java.util.*;

class Solution {
    public static class Point{
		int x;
        int y;
        
        Point(int x,int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int[][] map;
    static boolean redEnd, blueEnd;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][][] visited;
    
    static int MAX = Integer.MAX_VALUE;
    public int solution(int[][] maze) {
        Point red = null;
        Point blue = null;
        
        map = new int[maze.length][maze[0].length];
        visited = new boolean[maze.length][maze[0].length][2];
        
        for(int i=0; i<maze.length; i++) {
            for(int j=0; j<maze[0].length; j++) {
                map[i][j] = maze[i][j];
                
                //수레 시작 위치 초기화해
                if(maze[i][j] == 1) red = new Point(i,j);
                else if(maze[i][j] == 2) blue = new Point(i,j);
				
            }
        }
        //첫 시작위치를 방문처리를 한다
        visited[red.x][red.y][0] = true;
        visited[blue.x][blue.y][1] = true;
        
        int answer = backTracking(red,blue,0);
        return (answer == MAX) ? 0 : answer;
    }

    //움직일 수 있는지 판단하는 Logic
    private static boolean isPossible(Point curRed, Point nextRed, Point curBlue, Point nextBlue) {
        //좌표 범위 밖이면
        if(nextRed.x < 0 || nextRed.y < 0 || nextRed.x >= map.length || nextRed.y >= map[0].length || 
          nextBlue.x < 0 || nextBlue.y < 0 || nextBlue.x >= map.length || nextBlue.y >= map[0].length || map[nextRed.x][nextRed.y] == 5 || map[nextBlue.x][nextBlue.y] ==5 ) return false;
        
        //두 수레 겹치는거 쳌
        if((curRed.x == nextBlue.x && curRed.y == nextBlue.y) && (curBlue.x == nextRed.x && curBlue.y == nextRed.y)) {
            return false;
        }
    	
        //중복 방문이라면? && 자신의 도착 칸에 위치한 수레는 움직이지 않는것 체크
        if((!redEnd && visited[nextRed.x][nextRed.y][0]) || (!blueEnd && visited[nextBlue.x][nextBlue.y][1])) return false;
        
        //두 수레가 동일 위치일 경우?
        if(nextRed.x == nextBlue.x && nextRed.y == nextBlue.y) return false;
        
        return true;
    }
    //다음 Point로 움직이는 Logic
    private static Point nextPoint(int x,int y,int dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        return new Point(nx,ny);
    }
 	//백 트랙킹 
    private static int backTracking(Point red, Point blue, int count) {
        Point nextRed;
        Point nextBlue;
        int answer = MAX;
    	if(redEnd && blueEnd) return count; // 두 수레가 모두 도착일 경우의 최솟값 리턴
        
		for(int i=0; i<4; i++) {
            for(int j=0; j<4; j++) {
                //도착지점 -> 움직임 스탑
                nextRed = (!redEnd) ? nextPoint(red.x,red.y,i) : red;
                nextBlue = (!blueEnd) ? nextPoint(blue.x,blue.y,j) : blue;
                
                if(!isPossible(red,nextRed,blue,nextBlue)) continue;
                
                visited[nextRed.x][nextRed.y][0] = true;
                visited[nextBlue.x][nextBlue.y][1] = true;
                
                if(map[nextRed.x][nextRed.y] == 3) redEnd = true;
                if(map[nextBlue.x][nextBlue.y] == 4) blueEnd = true;
                
                answer = Math.min(answer,backTracking(nextRed,nextBlue,count+1));
                
                redEnd = false;
                blueEnd = false;
                visited[nextRed.x][nextRed.y][0] = false;
                visited[nextBlue.x][nextBlue.y][1] = false;
                
            }
        }
        
        return answer;
    }
}