[2020 카카오 인턴십] 경주로 건설 (JAVA)

문제

---

풀이

4시간동안 풀었다.. 머리 깨진다!

BFS + DP로 풀었는데, 거의 다 풀어놓고 dp 배열을 잘못 선언하는 바람에 끝까지 풀어내지는 못했다ㅠㅠ

처음에 dp를 3차원 배열로 두고 direction마다 최솟값을 저장하도록 했는데, 아무리 생각해도 메모이제이션을 잘 활용할 수가 없었다. 이 때 dp를 2차원 배열로 바꿔서 한 값만 저장하도록 했으면 됐을텐데 그걸 떠올리지 못했다..! 결국 그 좌표에 해당하는 최소비용을 저장하면 되니까, 뭘 어떻게 저장하고 활용할지 빨리 파악하고 결정하는 능력을 길러야 할 것 같다.

그리고 이미 방문한 루트를 재탐색하지 않기 위한 처리를 해주는 방식도 제대로 떠올리지 못했다. board[i][j]를 방문했다는 의미에서 INVALID로 값을 갱신하는 방식을 시도했는데, 경로 자체는 더 멀지만 비용은 더 저렴한 루트가 정답인 경우에서 예외가 발생했다. 그래서 다른 방식을 생각해봤는데 아무리 생각해도 떠오르지 않았다흐흑..ㅠㅠ

구글링을 해보니 dp를 2차원으로 활용하고, queue에 추가탐색 좌표를 추가하는 조건에 이를 활용하는 것이 내가 놓친 부분이었다. BFS로 접근해야 한다는 것과 direction에 따라 한 칸의 cost를 구하는 것은 스스로 떠올렸으니 칭찬칭찬..ㅎㅎ....

반 년 전에 이 문제를 처음 접했을 때는 그냥 꼴도 보기 싫을 정도로 어려워보였는데 이제는 반쯤은 스스로 풀 수 있는 정도는 된 것 같다. 열~~심히 하지는 않아서 속도가 더디긴 하지만, 앞으로 더 빡세게 알고리즘 밭에서 구르면 금방 성장할 수 있을 거라 믿는다... 홧팅..

---

코드

import java.util.*;

class Solution {

    private static final int VALID = 0;
    private static final int INVALID = 1;
    private static final int LINE = 100;
    private static final int CORNER = 500;
    private static final int MAX = 25;

    private static final int START = -1;
    private static final int[] dy = {0, 0, 1, -1};
    private static final int[] dx = {-1, 1, 0, 0};

    private int n;
    private int minCost = Integer.MAX_VALUE;
    private int[][] dp = new int[MAX][MAX];

    public int solution(int[][] board) {
        n = board.length;
        bfs(board);
        return minCost;
    }

    private void bfs(int[][] board) {
        Queue<Position> queue = new LinkedList<>();
        queue.offer(new Position(0, 0, 0, START));
        while (!queue.isEmpty()) {
            Position current = queue.poll();

            if (current.y == n - 1 && current.x == n - 1) {
                minCost = Math.min(minCost, current.cost);
                continue;
            }

            int ny, nx, nc;
            for (int direction = 0; direction < 4; direction++) {

                ny = current.y + dy[direction];
                nx = current.x + dx[direction];
                if (outOfBound(ny, nx) || board[ny][nx] == INVALID) continue;

                nc = calcCost(current, direction);
                Position next = new Position(ny, nx, nc, direction);
                
                if (dp[ny][nx] == 0 || dp[ny][nx] >= nc)
                    queue.offer(next);

                if (dp[ny][nx] == 0) dp[ny][nx] = nc;
                else dp[ny][nx] = Math.min(dp[ny][nx], nc);
            }
        }
    }

    private boolean outOfBound(int ny, int nx) {
        return ny < 0 || ny >= n || nx < 0 || nx >= n;
    }

    private int calcCost(Position current, int nextDirection) {
        int cost = current.cost + LINE;
        if (current.direction != START && current.direction != nextDirection) cost += CORNER;
        return cost;
    }
}

class Position {
    int y;
    int x;
    int cost;
    int direction;

    public Position(int y, int x, int cost, int direction) {
        this.y = y;
        this.x = x;
        this.cost = cost;
        this.direction = direction;
    }
}