[프로그래머스] 게임 맵 최단거리

풀이

일반적인 bfs 문제였다. 방문 배열 사용대신, 기존 maps 함수에 누적 거리 합을 음수로 표현했다. 음수로 표현한 이유는 기존 maps 배열에 값이 1인 좌표가 존재했기에 겹칠 수 있어서 그렇다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Node{
    int end;
    int weight;

    Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
}
public class Main {

    static int V;
    static int E;
    static int K;
    static int[] dist; // 시작 정점으로부터 각 정점까지의 최단거리
    static ArrayList<Node>[] g;
    static PriorityQueue<Node> pq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 정점의 개수
        dist = new int[V+1];
        g = new ArrayList[V+1];
        for(int i = 1; i <= V; i++) dist[i] = Integer.MAX_VALUE;
        for(int i = 1; i <= V; i++) g[i] = new ArrayList<>();
        E = Integer.parseInt(st.nextToken()); // 간선의 개수
        K = Integer.parseInt(br.readLine()); // 시작 정점 번호

        // 간선정보 입력 받음
        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int fn = Integer.parseInt(st.nextToken());
            int sn = Integer.parseInt(st.nextToken());
            int dst = Integer.parseInt(st.nextToken());
            g[fn].add(new Node(sn, dst));
        }
        // 다익스트라 수행

    }

    // 다익스트라 함수, node 는 시작 정점을 의미한다.
    static void dijkstra(int node){
        dist[node] = 0;
        pq.offer(new Node(node, 0));

        while(!pq.isEmpty()){
            Node n = pq.poll();
            for(Node nn: g[n.end]){
                // 현재 기록된 최단 거리 < n까지의 치단거리 + n->
                if(dist[n.end] < dist[n.end]+nn.weight)
            }
        }
    }


}