743. Network Delay Time

743. Network Delay Time

class Solution {
    private int[][] graph;
    private int[] visited;

    public int networkDelayTime(int[][] times, int n, int k) {
        this.makeGraph(times, n);
        this.visited = new int[n+1];

        int answer = -1;

        Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p[0]));
        pq.offer(new int[]{0, k});

        while(!pq.isEmpty()) {
            var next = pq.poll();

            if (visited[next[1]] != 0) continue;
            else visited[next[1]] = 1;
            if (Arrays.stream(this.visited).sum()==n) return next[0];

            var array = this.graph[next[1]];
            for (int i=1; i<n+1; i++) {
                if (array[i] < 0) continue;
                pq.offer(new int[] {array[i] + next[0], i});
            }
        }
        return answer;
    }

    private void makeGraph(int[][] times, int n) {
        this.graph = new int[n+1][n+1];
        for (int[] array : graph) {
            Arrays.fill(array, -1);
        }
        for (int[] edge : times) {
            this.graph[edge[0]][edge[1]] = edge[2];
        }
    }

}

 

bfs 최단 거리 문제
다른 사람들 풀이를 보았을 때, 굳이 우선순위 큐를 사용할 필요가 없는 것 같다.
특정 한 점까지의 최단 거리만 구하는 문제가 아니고, 결국 전체를 다 순회해야 하기 때문인 듯?

아직 알고리즘 문풀 도구로는 익숙하지 않은 자바로 풀어서 더 헷갈리는 거 같기도 하고,
어쨌든 힙은 좋은 도구이니까 힙을 자바에서 얼른 더 익숙하게 쓰고 싶어서 그냥 꺼내 쓴다.

자바 알고리즘 풀이 코드를 보면 기본 array 를 많이 사용한다. 아무래도 배열이 시간 효율성이 좋아서 일 것 같다..
이런 풀이법이 dp나 인덱스에 약한 나에게 좋은 연습이 될 거 같다.

지금 풀이는 썩 마음에 들지 않지만... 자바에 익숙해지면 더 좋아질 것이라고 생각한다.