문제

https://www.acmicpc.net/problem/1916

풀이 생각
bfs처럼 방문했는지 안했는지 판단하는 boolean 배열생성.
queue에 담아서 비교하고 비용을 넣었다 뺐다 하며 판단.

소스코드

Main

   static List<Node>[] list;
    static int[] dp;
    static boolean[] check;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        list = new ArrayList[n+1];
        // 노드를 담을 리스트
        dp = new int[n+1];
        // 도착지점
        check = new boolean[n+1];
        //방문 여부 배열

        for(int i=1; i<n+1; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            list[from].add(new Node(to,cost));
        }

        st = new StringTokenizer(br.readLine());
        int start= Integer.parseInt(st.nextToken());
        int destination = Integer.parseInt(st.nextToken());


        dijkstra(start);
        System.out.println(dp[destination]);

    }

Dijkstra

static void dijkstra(int start) {
        Queue<Node> q = new PriorityQueue<>();
        //우선순위 큐
        Arrays.fill(dp, Integer.MAX_VALUE);
        //dp에 해당 maxValue로 값을 채운다. 일괄 초기화.
        q.add(new Node(start,0));
        // 노드를 생성해서 큐에 넣는다. 0에서 시작.
        dp[start] =0;

        while(!q.isEmpty()) {
            Node node = q.poll();
            //초기값을 출력,
            int to = node.to;
            // 다음 출발 장소(노드를 받는다.)

            if(check[to]) continue;
            //들린적이 있다면, 계속 진행.

            check[node.to] = true;
            //true로 바꿔준후
            for(Node next : list[to]) {
                //foreach문으로 뽑아낸다
                if(dp[next.to] >= dp[to] + next.cost) {
                    //현재방문한 거리보다  최소비용인 곳이 있다면
                    dp[next.to] = dp[to] + next.cost;
                    // 값을 갱신하고 , add
                    q.add(new Node(next.to, dp[next.to]));
                }
            }
        }
    }
}

Node

class Node implements Comparable<Node>{
    int to;
    // 도착위치
    int cost;
    // 비용.

    public Node(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }
}

풀이방법

다익스트라라는 알고리즘이 있었다.
bfs느낌으로 방문했는지 판단후 가장 가중치가 작은애로 업데이트
노드를 비교하는 방법에 대해서도 더 공부

생각할 것

트리 구조, bfs dfs에 대한 공부

참고

https://loosie.tistory.com/166
https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-1916%EB%B2%88-%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-java