[Lv.3] 등산 코스 정하기 -자바

실패 코드 (시간초과, 메모리 초과)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[2];
        int[][] memo=new int[n+1][n+1];   //해당 경로까지의 intensity
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i+1][j+1]=(i==j)? 0:Integer.MAX_VALUE;
            }
        }
        for (int[] path : paths) {
            memo[path[0]][path[1]]=memo[path[1]][path[0]]=path[2];
        }
        Set<Integer> gateSet=new HashSet<>();
        Set<Integer> summitSet=new HashSet<>();
        for (int gate : gates) {
            gateSet.add(gate);
        }
        for (int summit : summits) {
            summitSet.add(summit);
        }

        for (int i = 1; i <= n; i++) {
            //경유지가 만약 쉼터가 아니라면 점검하지 않는다.
            if(gateSet.contains(i)||summitSet.contains(i))
                continue;
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    if((gateSet.contains(j)&& gateSet.contains(k))||(summitSet.contains(j)&&summitSet.contains(k))){
                        //j,k모두 출발지 or 산봉우리인 경우 해당 경로는 최댓값으로 바꾼다.
                        memo[j][k]=memo[k][j]=Integer.MAX_VALUE;
                    }else
                        memo[j][k]=memo[k][j]=Math.min(memo[j][k],Math.max(memo[j][i],memo[i][k]));
                }
            }
        }

        int intensity=Integer.MAX_VALUE;
        int node=n+2;
        for (int i = 0; i < gates.length; i++) {
            for (int j = 0; j < summits.length; j++) {
                if(intensity>memo[gates[i]][summits[j]]){
                    intensity=memo[gates[i]][summits[j]];
                    node=summits[j];
                }else if(intensity==memo[gates[i]][summits[j]]){
                    node=Math.min(node,summits[j]);
                }
            }
        }
        answer[0]=node;
        answer[1]=intensity;
        return answer;
    }
}

처음엔 dfs로 접근해봤으나 시간초과가 발생하여 그래프 탐색 알고리즘 중 하나인 플로이드 와샬 알고리즘을 이용해서 풀어보려 했다.

근데, 이 코드 또한 시간초과 및 메모리 초과가 발생했다..

결국 카카오에서 제공하는 해설을 참고해서 문제를 다시 풀어보았다.

 

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[2];
 		Queue<int[]> queue=new LinkedList<>();
        int[] weight=new int[n+1];
        Set<Integer> gateSet=new HashSet<>();
        Set<Integer> summitSet=new HashSet<>();
        Map<Integer, List<Node>> integerNodeMap=new HashMap<>();

        Arrays.fill(weight,Integer.MAX_VALUE);
        for (int gate : gates) {
            gateSet.add(gate);
            //gate번까지 0의 cost로 왔다.
            queue.add(new int[]{gate,0});
            //gate까지 0의 cost로 왔으니 gate까지 intesity는 0
            weight[gate]=0;
        }
        for (int summit : summits) {
            summitSet.add(summit);
        }
        for (int i = 0; i < n; i++) {
            List<Node> list = new ArrayList<>();
            integerNodeMap.put(i+1,list);
        }
        for (int[] path : paths) {
            if(gateSet.contains(path[0])||summitSet.contains(path[1]))
                integerNodeMap.get(path[0]).add(new Node(path[1],path[2]));
            else if (summitSet.contains(path[0])|| gateSet.contains(path[1]))
                integerNodeMap.get(path[1]).add(new Node(path[0],path[2]));
            else {
                integerNodeMap.get(path[0]).add(new Node(path[1],path[2]));
                integerNodeMap.get(path[1]).add(new Node(path[0],path[2]));
            }
        }

        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int node=poll[0];
            int cost=poll[1];
            //만약 노드까지의 weight보다 이번 poll을 이용해서 가는게 더 비싸다면 pass
            if(weight[node]<cost)
                continue;
            for (Node nd : integerNodeMap.get(node)) {
                int nextW=Math.max(nd.cost,weight[node]);
                if(weight[nd.n]>nextW){
                    weight[nd.n]=nextW;
                    queue.add(new int[]{nd.n,nextW});
                }
            }
        }

        Arrays.sort(summits);
        answer[0]=answer[1]=Integer.MAX_VALUE;
        for (int summit : summits) {
            if(answer[1]>weight[summit]){
                answer[1]=weight[summit];
                answer[0]=summit;
            }

        }
        return answer;
    }
    class Node{
        int n;
        int cost;

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

이 문제의 경우 가장 중요한 아이디어는 출발지와 산봉우리의 설정 인 것 같다.

목적지까지 가는 경로에 다른 출발지나 탐색하는 산봉우리를 제외한 산봉우리를 포함하면 안된다.

따라서, 출발지에선 출발만 할 수 있게 산봉우리에선 들어올 수만 있게 방향을 하나로 바꾸면 해당 경우를 만족할 수 있게 된다.

 

그 후, 다익스트라로 현재 노드까지의 최소 intensity와 현재 노드로의 비용 Cost를 비교하여 가능한 경로라면 현재 노드에서 갈 수 있는 다른 노드들을 선회하며 갱신의 가능성이 있는 노드로 탐색을 추가적으로 진행한다.

 

또 살짝 중요하다고 생각되는 부분은 다익스트라 탐색 시 노드 하나씩 잡고 쭉 돌고 다시 와서 최소 intensity, 산봉우리 이렇게 갱신하고 다음 출발지 노드 똑같이 반복하는 형식으로 하는 경우 시간초과가 나게된다.

그러므로, 큐에 다같이 넣고 탐색하여 시간을 줄일 수 있다.

 

이번 문제는, 좀 어렵게 느껴졌던 문제였다.

다익스트라 알고리즘이라는 느낌이 들긴 했지만 시간초과가 날 것 같아 플로이드 와샬로 풀어보려 했으나 출발지,산봉우리 설정부분을 생각하지 못하여 실패하였고 다익스트라는 무조건 출발지 하나에서 출발해서 쭉 돌고 갱신하는 형식만 생각했기에 출발지를 한번에 다 넣고 검사하는 방법을 떠올리지 못해 다익스트라로 문제를 풀 시도조차 하지않았다.

 

계속 하다보면 Lv3정도는 대부분 힘들이지 않고 풀 수 있는 정도가 되지 않을까 ..? 

열심히 해야겠다