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

in Algorithm on 그래프 이론

https://school.programmers.co.kr/learn/courses/30/lessons/159993

풀이

(0, 0)에서 (N-1, N-1)까지 이동해야한다.

1은 벽을 의미하므로 0만을 통과해서 갈 수 있고, 직선도로는 100, 코너는 500이 필요하다.

즉, 방향을 같이 저장하여 방향이 달라지면 코너가 생기는 것이므로 500을 추가하고, 항상 100을 추가하면 된다.

방향을 같이 저장하면서 bfs탐색을 진행했고,

비용을 최소로 해야하기때문에 board 이차원배열에 비용을 같이 저장하면서 진행했다.

메모리: 93.6MB

시간: 0.43ms

언어: Java 11

코드

import java.util.*;

class Solution {
    static class Node {
        int r;
        int c;
        int dir;
        int cost;

        public Node(int r, int c, int dir, int cost) {
            this.r = r;
            this.c = c;
            this.dir = dir;
            this.cost = cost;
        }
    }

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    public int solution(int[][] board) {
        int len = board.length;
        for(int i = 0; i < len; i++) {
            for(int j = 0; j < len; j++) {
                if(board[i][j] == 0){
                    board[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        return bfs(board);
    }

    private int bfs(int[][] board) {
        int len = board.length;

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(0, 0, -1, 0));

        boolean[][][] visit = new boolean[len][len][4];
        for(int i = 0; i < 4; i++) {
            visit[0][0][i] = true;
        }

        board[0][0] = 0;

        int ans = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            Node cur = queue.poll();

            if(cur.r == len - 1 && cur.c == len - 1) {
                ans = Math.min(ans, cur.cost);
                continue;
            }

            for(int i = 0; i < 4; i++) {
                int nr = cur.r + vector[i][0];
                int nc = cur.c + vector[i][1];

                if(nr < 0 || nc < 0 || nr >= len || nc >= len || board[nr][nc] == 1) {
                    continue;
                }

                int tmp = 100;
                if(cur.dir != -1 && cur.dir != i) {
                    tmp += 500;
                }

                if(!visit[nr][nc][i] || cur.cost + tmp <= board[nr][nc]) {
                    queue.add(new Node(nr, nc, i, cur.cost + tmp));
                    board[nr][nc] = cur.cost + tmp;
                    visit[nr][nc][i] = true;
                }

            }
        }

        return ans;
    }
}