2020 카카오 인턴십 - 경주로 건설

Java

2020 카카오 인턴십 - 경주로 건설

문제

문제 출처

접근 방법

먼저 각 지점까지 도착하는 최소 비용을 담는 2차원 배열 cost[][]를 N X N 만큼 지정한다.

DFS를 사용하여 목표하는 점까지 최소 비용을 구하였다.
(0,0)부터 시작하여 [상,하,좌,우]로 하나씩 탐색한다.
해당 하는 위치까지 도달하는 비용이 현재 cost 배열에 저장된 값보다 작으면 갱신하고, 이 점을 다음으로 탐색한다.

하지만 위의 DFS의 방법으로는 테스트 케이스 14번을 해결하지 못한다.
이유는 현재 지점에서 다음 지점으로 어떤 방향으로 먼저 탐색하는가에 따라 답이 달라 질 수 있다.

처음에 [상,하,좌,우]로 탐색하여 다음 지점을 찾도록 하였는데, 이는 오른쪽 보다 아래를 먼저 탐색하게 된다.

위 사진 처럼 빨간 색 선을 따라 먼저 탐색하여 분홍색 위치 까지 도달하게 되면,
빨간 색 선을 따라 먼저 도착한 해당 분홍색 위치의 비용은 초록색 선을 따라 간 분홍색 위치보다 가격이 더 저렴하게 되어, 이후 실제 답인 초록색 선이 더 이상 진행 할 수 없게 된다.

따라서, 하 -> 우 로 탐색이 아닌, 우 -> 하 로 탐색 순서를 바꾸면 해결된다.

하지만 여전히 불안한 부분이 있으므로, BFS로 탐색하는 것이 더 나은 대안이라고 생각된다.

코드

import java.util.*;

class Solution {
	static int[][] map, cost;
	static int n;
    public static int solution(int[][] board) {
        int answer = 0;
        n = board[0].length;
        map = new int[n][n];
        cost = new int[n][n];
        for(int i = 0; i < board.length; i++) {
        	map[i] = board[i].clone();
        	Arrays.fill(cost[i], Integer.MAX_VALUE);
        }

        cost[0][0] = 0;
        DFS(0,0,0,-1);

        return answer = cost[n-1][n-1];
    }
    // 우, 하, 상, 좌
    static int[] dy = {0,1,-1,0};
    static int[] dx = {1,0,0,-1};

    public static void DFS(int y, int x, int curCost, int lastDir) {
    	int ny,nx, cal;
    	for(int i = 0; i < 4; i++) {
    		ny = y + dy[i];
    		nx = x + dx[i];

    		if(isIn(ny,nx)) {
    			if(i == lastDir || lastDir == -1)	// 직선이거나, 시작 점일 때
        			cal = curCost + 100;
        		else
        			cal = curCost + 600;		// 방향이 꺾이면

    			if(cost[ny][nx] >= cal && map[ny][nx] == 0) {
	    			cost[ny][nx] = cal;
	    			DFS(ny,nx,cal,i);
    			}
    		}
    	}

    }
     // 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= n)
            return false;
        return true;
    }
}

후기 및 개선할 점

이후 다시 이 문제를 풀 때는 BFS로 해결한다.