[Algorithm] 프로그래머스 - 등산코스 정하기

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 프로그래머스 등산코스 정하기 문제를 해결한 과정을 정리하도록 하겠습니다.

 

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/118669#

프로그래머스

 

 

1. 문제 해결 방안

 

해당 문제는 n번 노드로 도착하는 과정에서 하나의 특정 경로가 거친 가중치들 중 가장 큰 가중치를 intensity로 설정합니다.
만약 n번 노드로 도착할 수 있는 경로가 여러 개 일 때, 특정 경로들의 intensity를 비교하여 가장 작은 intensity를 선정합니다.

 

즉 to 노드는 from 노드의 intensity와 from과 to 노드 사이의 간선의 가중치 중 더 큰 값을 distance로 설정한 후,
distance = max(intensity[from.노드 번호], edge(from.노드번호, to.노드 번호))

 

to 노드의 노드 번호에 있는 intensity의 값보다 distance가 더 작다면 intensity를 distance로 업데이트해야 합니다.

if intensity[to.노드 번호] > distance: intensity[to.노드 번호] = distance

 

시작은 gates 배열에서 gate를 큐에넣는 방식으로 다익스트라 알고리즘을 활용할 수 있습니다.

 

 

 

2. 소스

 

import java.util.*;

class Solution {
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        Graph graph = new Graph(n);
        graph.setGate(gates);
        graph.setSummit(summits);
        
        for (int[] path : paths) {
            int s = path[0];
            int d = path[1];
            int w = path[2];
            
            graph.addEdge(s, d, w);
        }

        return graph.dijkstra(n, gates, summits);
    }
}


class Graph {
    
    Set<Integer> gateSet = new HashSet<>();
    Set<Integer> summitSet = new HashSet<>();
    List<List<Node>> nodes = new ArrayList<>(); // nodes의 i번 인덱스에는 i번이 갈 수 있는 adjacent 
    
    class Node {
        int d; // 만약 새로 출발하는 노드 == queue에 넣어야 하는 노드(to) 라면 도착해야하는 노드의 주소, 이미 도착했다면 == queue에서 나온 노드(from) 도착한 현재 노드 번호
        int w; // 도착지 노드로 가는데 필요한 가중치, 만약 이 노드가 출발 노드라면 이 노드로 도착하는데 필요했던 가중치
        
        Node (int d, int w) {
            this.d = d;
            this.w = w;
        }
    }
    
    Graph(int n) {
        for (int i = 0; i <= n; i++) nodes.add(new ArrayList<>());
    };
    
    void setGate(int[] gates) {
        for (int gate : gates) {
            gateSet.add(gate);
        }
    }
    
    void setSummit(int[] summits) {
        for (int summit : summits) {
            summitSet.add(summit);
        }
    }
    
    void addEdge(int s, int d, int w) {        
        if (gateSet.contains(s) || summitSet.contains(d)) {
            nodes.get(s).add(new Node(d, w)); // 만약 s가 게이트라면 출발 노드만 존재 or d가 정상이라면 도착 노드만 존재
        } else if (gateSet.contains(d) || summitSet.contains(s)) {
            nodes.get(d).add(new Node(s, w)); 
        } else {
            nodes.get(d).add(new Node(s, w)); 
            nodes.get(s).add(new Node(d, w));   
        }
    }
    
    int[] dijkstra(int n, int[] gates, int[] summits) {
        
        Queue<Node> queue = new ArrayDeque<>();
        int[] intensity = new int[n + 1]; 
        
        Arrays.fill(intensity, Integer.MAX_VALUE);
        
        for (int gate : gates) {
            queue.add(new Node(gate, 0)); // gate로 도착하는 가중치는 0 (출발지이므로)
            intensity[gate] = 0;
        }
        
        while(!queue.isEmpty()) {
            Node from = queue.poll(); // 현재 도착한 노드는 출발 노드로 변경

            for (int i = 0; i < nodes.get(from.d).size(); i++) {
                Node to = nodes.get(from.d).get(i);
                
                int distance = Math.max(intensity[from.d], to.w);
                if (intensity[to.d] > distance) {
                    intensity[to.d] = distance;
                    queue.add(new Node(to.d, distance));
                }
            }            
        }
        
        int summit = Integer.MAX_VALUE; 
        int intense = Integer.MAX_VALUE;
        
        Arrays.sort(summits); // 만약 intense가 같다면 가장 작은 정상 번호를 구해야함
        
        for (int sm : summits) {
            if (intensity[sm] < intense) {
                summit = sm;
                intense = intensity[summit];
            }
        }
        
        return new int[]{summit, intense};
        
    }
    
}

 

 

3. 부분 해결 과정

 

while(!queue.isEmpty()) {
            Node from = queue.poll(); // 현재 도착한 노드는 출발 노드로 변경

            for (int i = 0; i < nodes.get(from.d).size(); i++) {
                Node to = nodes.get(from.d).get(i);
                
                int distance = Math.max(intensity[from.d], to.w);
                if (intensity[to.d] > distance) {
                    intensity[to.d] = distance;
                    queue.add(new Node(to.d, distance));
                }
            }            
        }

 

이 코드는 queue에서 나온 노드는 from, queue에 넣을 노드를 to로 설정하였습니다.

즉, 다음 목적지로 가야 할 노드에 설정된 w와 출발지까지 오는 과정에 설정된 노드의 intensity를 비교하여
더 큰 값을 distance로 설정합니다. (distance는 문제의 요구사항에 맞춰 현재까지 온 경로 중에 가장 큰 값으로 설정해야 함)

 

만약 다음 목적지로 가야할 곳의 intensity값 보다 새로 온 경로의 distance가 더 작다면 문제의 요구사항에 의해
더 작은 intensity를 설정해야 합니다.

 

이 코드의 진행 순서를 정리하면 다음과 같습니다.

 

• from gate: 1, summit: 4
  edge => (1, 2, 3), (1, 3, 1)
  edge => (2, 4, 7), (3, 4, 1)
• gate.d: 1, gate.w: 0 설정
• while 루프 시작       
  
  nodes.get(1) -> [2, 3]
  
  1) if from d = 1, w = 0, 도착지 2로 갈 때,
  2) Node to => d = 2, w = 3
  3) distance = max(intensity[from.d], to.w)
  -----> intensity[from.d] => intensity[1] = 0, to.w = 3, 고로 distance = 3
  4) intensity[2] > distance 이므로, intensity[2] = 3
  5) queue (new Node(2, 3))
          
  6) if from d = 1, w = 0, 도착지 3으로 갈 때,
  7) Node to => d =  3, w = 1 
  8) 앞의 도착지 2로 갈 때와 같은 방법으로 distance 계산 -> distance = 1
  9) 앞의 intensity[] > distance 비교와 같은 방법으로 계산 -> intensity[3] = 1
  10) queue (3, 1)
          
  11) if from d = 2, w = 3, 도착지 4로 갈 때
  12) Node to = nodes.get(2) -> d =  4 w = 7
  13) intensity[2] =  3, to.w = 7 이므로 distance = 7
  14) intensity[4] = distance = 7
  15) queue (4, 7) ----> graph.get(4).size() == 0 (도착 노드이므로) --> 종료
          
  16) if from d = 3, w = 1, 도착지 4로 갈 때
  17) Node to = nodes.get(3) -> d = 4, w = 1
  18) intensity[3] = 1, to.w = 1로 distance = 1
  19) intensity[4] > distance (앞에서 7로 업데이트 되었으므로 ) 성립하므로  intensity[4] = distacne = 1
  20) queue (4, 1) ----> graph.get(4).size() == 0 ---> 종료
  
  따라서, summit 4, intensity[4] = 1가 됩니다.

 

이상으로 프로그래머스 등산코스 정하기 정리를 마치도록 하겠습니다.