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

1. 링크

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

프로그래머스

2.  

3. 분류

길찾기 (다익스트라 등)

완전 탐색

4.  

5. 개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

6.  

7. 핵심 알고리즘

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

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

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

8.  

9. 시행착오

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

visited를 공통으로 사용함.

10.  

11. 코드

      

      

      

    
    

      <java />
    

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;
        }
    }
}