[프로그래머스] 경주로 건설 (자바)

 

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

BFS로 풀었습니다. 처음에 쉽게 DFS로 도전했다가 시간 초과로 실패했네요. 

차의 방향은 총 4방향입니다. 상, 우, 하, 좌(U, R, D, L - 0, 1, 2, 3)

그래서 한 칸에 들어갈 수 있는 총경우의 수는 4가지이므로 방문을 체크할 때 3차원 배열을 이용했습니다.

 

이 문제에서 주의해야할 점은 코너를 돌면 500원이 아닌 600원을 더해줘야 한다는 점입니다.

직접 손으로 따라가면서 이해하면 됩니다.

 

100원인 경우는 0 -> 0, 2 || 1 -> 1, 3 || ... 등 직진을 하는 경우입니다.

후진의 경우 귀찮아서 제외하지 않았습니다. 어차피 걸러집니다.

 

600원일 경우에는 0 -> 1, 3 || 1 -> 0,2 || .... 등입니다.

잘 보면 2로 나누었을 때 나누어 떨어짐과 안 떨어짐이 있습니다.

코너의 특성상 90도를 회전하는데 일부러 차량 회전 배치를 상-우-하-좌로 하여 1씩 증가하고 2칸마다 짝을 짓도록 했습니다.

---

전역 변수

dx[], dy [] = 차의 방향을 정하는 배열(상, 우, 하, 좌)

map [][] = 문제에서 주어진 지도

value [][][] = 방문을 체크할 배열

n = map의 길이

answer = 정답

메소드

int [] solution

map, value 등 전역 변수를 초기 값으로 세팅합니다.

그리고 drive 함수가 끝나면 도착지의 값들 중 가장 작은 값을 반환합니다.

(drive 호출)

 

void drive

BFS를 통해 목표까지 갑니다. 이미 방문했더라도 더 싸게 갈 수 있는 경우가 있다면 최적화해줍니다.

현재 위치와 목표 위치에 따라 100원 및 600원을 추가합니다.

(check 호출)

 

boolean check

올바른 좌표값인지 확인하여 반환합니다.

 

class Car

좌표값 x, y를 가지고 방향인 dir, 현재까지의 비용인 cost를 가집니다.

 

int getCost

현재 위치에서 다음 위치로의 값을 구해줍니다.

설명했듯이 100원과 600원을 반환해줍니다.

 

import java.util.LinkedList;
import java.util.Queue;

public class pm경주로건설 {

	//U,R,D,L
	public int dx[] = {-1,0,1,0};
	public int dy[] = {0,1,0,-1};
	public int map[][];
	public int value[][][];
	public int n, answer;

	public int solution(int[][] map) {
		n = map.length;
		this.map = map;
		answer = Integer.MAX_VALUE;
		value = new int[4][n][n];

		for(int i = 0; i < 4; i++) 
			value[i][0][0] = 1;
		
		drive();
		for(int i = 0; i < 4; i++) 
			answer = Math.min(answer, value[i][n-1][n-1] == 0 ? Integer.MAX_VALUE : value[i][n-1][n-1]);

		return answer;
	}

	public void drive() {
		Queue<Car> q = new LinkedList<Car>();
		q.add(new Car(0, 0, -1, 0));

		while(!q.isEmpty()) {
			Car now = q.poll();
			
			if(now.x == n-1 && now.y == n-1) 
				continue;

			for(int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];

				//방문하지 않았거나 더 싸게 갈 수 있는 경우(최적화)
				if(check(nx, ny) && map[nx][ny] == 0 && (value[i][nx][ny] == 0 || value[i][nx][ny] > now.cost)) {
					if(now.dir == -1) {
						value[i][nx][ny] = 100;
						q.add(new Car(nx, ny, i, 100));
					}
					else {
						int nextCost = now.getCost(nx, ny);
						if(value[i][nx][ny] == 0 || now.cost + nextCost < value[i][nx][ny]) {
							value[i][nx][ny] = now.cost + nextCost;
							q.add(new Car(nx, ny, i, now.cost + nextCost)); 
						}
					}
				}
			}
		}
	}

	public boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < n && y < n; 
	}

	class Car {
		int x, y, dir, cost;

		Car(int x, int y, int dir, int cost) {
			this.x = x;
			this.y = y;
			this.dir = dir;
			this.cost = cost;
		}

		int getCost(int x, int y) {
			for(int i = 0; i < 4; i++) {
				int nx = this.x + dx[i];
				int ny = this.y + dy[i];

				if(nx == x && ny == y) {
					if(dir % 2 == 0) {
						if(i % 2 == 0)
							return 100;
						else
							return 600;
					}
					else {
						if(i % 2 == 1)
							return 100;
						else
							return 600;
					}				
				}
			}

			return 0;
		}
	}
}