[프로그래머스] 2020 카카오 인턴십 - 경주로 건설 - 자바(JAVA)

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

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

 

문제 해석

경주로는 N x N 크기의 정사각형 격자형 태이며 각 격자의 크기는 1 x 1입니다.

각 칸은 0 또는 1로 채워져 있으며 0은 비어있음, 1은 벽을 의미합니다.

출발점은 (0,0) 칸이며 도착점은 (N-1, N-1)입니다.

경주로는 상하좌우 인접한 두 칸을 연결하여 건설할 수 있습니다. (BFS, DFS 활용)

이때 벽이 있는 칸에는 건설할 수 없습니다. (제약조건 : 벽)

인접한 두 빈칸을 상하 또는 좌우로 연결한 경주로를 "직선 도로"라고 합니다.

직선도로가 서로 직각으로 만나는 지점을 코너라고 합니다.

직선도로를 만드는 비용은 100원이며 코너를 만드는 비용은 500원입니다.

이때 경주로를 건설하는데 필요한 최소 비용을 계산하세요

 

문제 풀이 전 설계

2차원 정사각 배열의 크기는 3 이상, 25 이하입니다.

벽이 존재하기 때문에 돌아가야 하는 경우가 있을 수 있습니다. (상하좌우를 탐색해야 합니다)

항상 경주로를 건설할 수 있는 형태로 주어집니다.

 

크기가 작기 때문에 완전 탐색이 가능해 보이기도 합니다.

무한루프를 방지하기 위해 DP [y좌표][x좌표][4방향]을 사용할 예정입니다.

 

이전의 방향을 기록해두다가 수직으로 꺾이는 순간을 체크하여 비용을 갱신해야 합니다.

즉, 직선도로와 코너를 잘 구분해야 합니다.

 

아니면 문제를 풀다 보니 다익스트라도 떠오릅니다.

PQ를 활용하여 직선도로에 우선순위를 주어 탐색해보고자 합니다.

 

문제 풀이하면서

처음에 코너를 500만 추가했다가 600을 추가해야 하는것을 알게되었습니다.

 

이후에 다익스트라로 구현해보니 14번 TC가 틀렸다고 나옵니다.

 

다음과 같은 반례 TC가 존재했습니다.

 

{0, 0, 0, 0, 0}

{0, 1, 1, 1, 0}

{0, 0, 1, 0, 0}

{1, 0, 0, 0, 1}

{0, 1, 1, 0, 0}

 

0,0을 기점으로 오른쪽으로 출발했을 때는 board [3][3]에서2300을,

0,0을 기점으로 아래쪽으로 출발했을 때는 board [3][3]에서 2100을 갖게 될 것입니다.

 

당장 [3][3]에서 출발했을 때 2300을 기준으로 [4][4]에 도달하면 3000이 되고

2100을 기준으로 도달하면 3300이 됩니다.

'코너'가 한번 더 발생하기 때문입니다.

 

만약 방향을 일방적으로 고려한 다익스트라를 구현한다면,

[3][3]에서 2300을 꺼냈을 때

다익스트라로 갱신한 최솟값 배열을 min_dist라고 한다면

이미 min_dist [3][3] 은 2100이기 때문에 continue 되면서 탐색하지 않게 됩니다.

 

 

즉, 다익스트라를 통해 '그 지점의 방향'에 대한 최솟값을 가지고 있어야 합니다.

min_dist [y][x][방향] 이렇게 3차원 배열로 해결 가능합니다.

 

 

해당 풀이를 매우 짧고 직관적으로 알 수 있는 풀이를 가져왔습니다.

Cost를 활용한 continue가 존재하기 때문에 visited배열은 필요 없습니다.

코드

import java.util.*;

public class Solution {
    public int solution(int[][] board) {
        int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1};
        int N = board.length;

        int[][][] cost = new int[N][N][4];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                Arrays.fill(cost[i][j], Integer.MAX_VALUE);

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0, 1});
        queue.add(new int[]{0, 0, 0, 3});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int k = 0; k < 4; k++) {
                int ny = cur[0] + dy[k], nx = cur[1] + dx[k];
                int c = cur[2] + (cur[3] == k ? 100 : 600);

                if (ny < 0 || nx < 0 || ny >= N || nx >= N || board[ny][nx] == 1 || cost[ny][nx][k] <= c) continue;
                cost[ny][nx][k] = c;
                queue.add(new int[]{ny, nx, c, k});
            }
        }

        return Arrays.stream(cost[N - 1][N - 1]).min().getAsInt();
    }
}

 

 

출처

https://girawhale.tistory.com/86

[프로그래머스] 경주로 건설 / 2020 카카오 인턴십 - JAVA

https://junho0956.tistory.com/354

Programmers 경주로 건설