[프로그래머스/Java] [2022 카카오 인턴십 기출문제] 등산코스 정하기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/118669

프로그래머스

 

 

🔍  해결 과정

💡 해결 요약: BFS를 통한 해결

 

시간 복잡도 문제로 고민을 엄청 했었던 문제입니다.

 

처음에는 반복문을 통해 출발지마다 BFS를 활용하여 특정 도착 지점마다 최소 intensity를 계산하는 방식으로 생각을 했지만 시간 복잡도로 인해서 이 방식은 사용할 수 없다고 판단했었습니다. 왜냐하면 최대 노드의 개수가 5만이고, 출발지도 최대 5만이기에 인접리스트에서 시간 복잡도 O(n + e) (n: 노드의 개수, e: 간선의 개수)을 가지는 BFS를 고려한다면 전체적인 시간복잡도는 O(n^2)으로 계산이 되기 때문입니다. (제 의견이 틀렸다면 댓글로 이유를 알려주시면 감사하겠습니다!)

 

그래서 다른 획기적인 방법이 없는지 고민을 하다가 다른 분들의 설명을 참고하였습니다. 결과적으로는 제가 생각했던 방식으로 해결이 가능했습니다. 왜 시간 초과가 나지 않은지는 아직 궁금증이 풀리지 않아서 댓글을 달아주시면 감사하겠습니다!

 

먼저 아래 그림과 같은 그래프가 있다고 가정합니다.

그림 1. 그래프

 

위 그림에서 파란색 노드 1번이 출발 지점이고, 주황색 노드 4번이 도착지점입니다. 

 

위 그림에서 1 -> 2 -> 4의 경로로 간다고 가정한다면 intensity의 값은 2이고, 1 -> 3 -> 4의 경로로 간다면 intensity의 값은 4입니다.

이 두 개의 intensity의 값 중 최솟값은 2이므로 이상적인 intensity의 값은 2가 됩니다.

즉 출발지점에서 BFS를 통해서 4번 지점까지 갔을 때의 intensity의 값을 계속 갱신을 해야하기에 intensity의 정보를 담을 테이블이 필요합니다. 저는 아래 코드에서 정수형 일차원 배열 d를 활용하였습니다.

d 테이블의 용도는 다음과 같습니다.

d[n]: n번 노드에 도착했을 때 나올 수 있는 intensity의 값 중 최솟값

 

단, 몇 가지 예외처리가 필요한데 출발 지점에서 산봉우리까지의 경로 중 또 다른 출발 지점이 존재하면 안되고, 다른 산봉우리도 나오면 안됩니다. 

 

위 그림 예시에서는 출발지와 산봉우리의 지점이 각각 한 개이지만, BFS를 통해서 d의 값들을 계속 갱신하면서도 위 예외 사항을 유념하면서 문제를 해결해야합니다.

 

그렇게 최종적으로 각 노드마다의 intensity 값이 완성되었다면, 문제에서 주어진 summits 배열을 활용하여 산봉우리 지점에서의 intensity의 값들 중 최솟값을 구하면 됩니다.

---

✏️ 코드 및 실행 결과

import java.util.*;

class ToNode {
    private final int index;
    private final int time;
    
    public ToNode(int index, int time) {
        this.index = index;
        this.time = time;
    }
    
    public int getIndex() {
        return index;
    }

    public int getTime() {
        return time;
    }
}

class Solution {
    
    private static final int INF = (int)1e9;
    
    private List<List<ToNode>> graph = new ArrayList<>();
    private int[] d;
    private Set<Integer> s_gates = new HashSet<>();
    private Set<Integer> s_summits = new HashSet<>();
    
    public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
        int[] answer = new int[]{0, INF};
        d = new int[n + 1]; // 해당 노드 번호까지의 치소 intensity(출발지 모두 통틀어서 계산)
        
        for (int g : gates) {
            s_gates.add(g);
        }
        
        for (int s : summits) {
            s_summits.add(s);
        }
        
        Arrays.fill(d, INF);
        
        // 그래프 초기화하기
        initGraph(n, paths);
        
        for (int g : gates) {
            bfs(g); // bfs를 통해서 각 노드로의 최대 intensity를 계속 갱신
        }
        
        // 산봉우리의 intensity가 같으면 -> 산봉우리 번호가 낮은 것부터
        for (int s : summits) {
            if (answer[1] < d[s]) {
                continue;
            }
            
            if (answer[1] == d[s]) {
                answer[0] = Math.min(answer[0], s);
                continue;
            }
            
            answer[0] = s;
            answer[1] = d[s];
        }
        
        return answer;
    }
    
    private void initGraph(final int n, final int[][] paths) {
        for (int i = 0; i <= n; ++i) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] path : paths) {
            int from = path[0];
            int to = path[1];
            int time = path[2];
            
            graph.get(from).add(new ToNode(to, time));
            graph.get(to).add(new ToNode(from, time));
        }
    }
    
    private void bfs(final int start) {
        Queue<ToNode> q = new ArrayDeque<>();
        q.add(new ToNode(start, 0));
        d[start] = 0;
        
        while (!q.isEmpty()) {
            ToNode node = q.poll();
            int curIdx = node.getIndex();
            int curTime = node.getTime();
            
            // 산봉우리인지 확인하기
            if (s_summits.contains(curIdx)) { // 시간복잡도 O(1)
                continue;
            }
            
            for (ToNode n : graph.get(curIdx)) {
                int nextIdx = n.getIndex();
                int nextTime = n.getTime();
                
                // 출발지점이라면 가면 안됨
                if (s_gates.contains(nextIdx)) {
                    continue;
                }
                
                int curIntensity = Math.max(curTime, nextTime);
                
                if (curIntensity >= d[nextIdx]) {
                    continue;
                }
                
                d[nextIdx] = curIntensity;
                q.offer(new ToNode(nextIdx, curIntensity));
            }
        }
    }
}

 

 

📜 실행 결과