[2022 카카오 인턴십 코테] 등산코스 정하기

링크

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

프로그래머스

 

분류

길찾기 (다익스트라 등)

완전 탐색

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

출발지에서 봉우리까지 가는 경로만 찾으면 됨. 봉우리에서 다시 원 출발지로 돌아오는 과정은 생각할 필요가 없음 (어쩌피 intensity가 같을 것이기 때문)

그 외에는 길찾기 알고리즘들을 변형시켜서 사용하거나

그래프 탐색(완전 탐색) 알고리즘 사용하면 됨

 

시행착오

처음엔 각 State마다 visited 를 만들어 사용했으나 유지하기 위한 리소스가 너무 많이 들어서

visited를 공통으로 사용함.

 

코드

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) nodes[i] = new Node(i);

        for (int i = 0; i < gates.length; i++) nodes[gates[i] - 1].isGate = true;
        for (int i = 0; i < summits.length; i++) nodes[summits[i] - 1].isSummit = true;

        for (int i = 0; i < paths.length; i++) {
            if (!nodes[paths[i][1] - 1].isGate) nodes[paths[i][0] - 1].paths.add(new Path(nodes[paths[i][1] - 1], paths[i][2]));
            if (!nodes[paths[i][0] - 1].isGate) nodes[paths[i][1] - 1].paths.add(new Path(nodes[paths[i][0] - 1], paths[i][2]));
        }

        Queue<State> queue = new LinkedList<>();
        for (int i = 0; i < gates.length; i++) queue.add(new State(nodes[gates[i] - 1]));

        int[] visited = new int[n];
        Arrays.fill(visited, 0x7FFFFFFF);

        int summitID = 0x7FFFFFFF, intensity = 0x7FFFFFFF;
        while (!queue.isEmpty()) {
            State s = queue.poll();

            if (s.node.isSummit) {
                if (s.node.id <= summitID && s.intensity == intensity || s.intensity < intensity) {
                    summitID = s.node.id;
                    intensity = s.intensity;
                }

                continue;
            }

            for (Path p : s.node.paths) {
                State newS = new State(p.to);
                newS.intensity = Math.max(s.intensity, p.cost);

                if (visited[p.to.id] <= newS.intensity) continue;
                visited[p.to.id] = newS.intensity;

                queue.add(newS);
            }
        }

        return new int[]{ ++summitID, intensity };
    }

    class Path{
        Node to;
        int cost;

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

    class Node{
        int id;
        List<Path> paths = new ArrayList<Path>();
        boolean isGate = false, isSummit = false;

        public Node(int id) {
            this.id = id;
        }
    }

    class State{
        int intensity = -1;
        Node node;

        public State(Node node) {
            this.node = node;
        }
    }
}