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

2022 카카오 인턴 코딩테스트 4번 등산 코스 정하기
https://school.programmers.co.kr/learn/courses/30/lessons/118669

실제 인턴 코테를 볼 때 풀지 못했던 문제이다. 이번에 다시 풀어보았는데 역시 어려웠고 약 4시간 정도를 고민하다 풀었다.

풀이

첫 번째 접근

DFS를 통해 모든 출입구에서 시작하여 가능한 경로를 전부 백트래킹으로 탐색하여 모든 경로에 대하여 가장 작은 intensity 를 찾는다.
-> 당연히 시간 초과

약 1시간 반 ~ 2시간 동안 고민...

두 번째 접근

1. 가장 작은 intensity 는 주어진 등산 코스의 간선 중 하나에 무조건 존재한다는 점
2. 1 <= w <= 10,000,000 이라는 점

두 점을 고려하여 이분 탐색으로 풀 수도 있겠다? 라는 생각을 하게 되었다.

1 ~ 10,000,000 사이의 값을 하나 정해서(이 값을 mid 로 정한다) BFS를 돌며 mid 보다 큰 간선은 지나가지 않고 산봉우리에 도착할 수 있는지 검사한다. 도착할 수 있는 산봉우리가 여러 개일 경우 가장 작은 산봉우리를 반환한다.

도착할 수 있는 산봉우리가 존재한다면, right 값을 줄여 더 작은 mid 값으로 검사를 반복한다.
도착할 수 있는 산봉우리가 없다면, left 값을 늘려 더 큰 mid 값으로 검사를 반복한다.
-> 시간 초과
-> 산봉우리에 해당하는 노드인지 검사하는 부분에서 O(N) 발생. O(1)으로 줄여서 다시 실행
-> 여전히 시간 초과

흐음... 30분 정도 고민..

이분 탐색을 하면서 한 번의 검사에서 여러 번의 gate에서 BFS를 실행시키는 것을 발견. 최대 n 번의 BFS를 한 번의 검사에서 하게 되는 상황이 발생 가능(아마 이 경우가 25번 케이스인 것 같다).

BFS를 돌릴 때, 한 번에 모든 출발 가능한 gate를 queue에 push하여 실행
-> 성공

C++ 코드

#include <bits/stdc++.h>

#define ll long long
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;

using namespace std;

vector<int> ans = {INF, INF};  // ans = {summit #, intensity}
vector<pair<int,int>> adj[50001];
int vi[50001];
int summitCheck[50001];
int gateCheck[50001];
int l=0, r=1e7;

int bfs(vector<int> &gates, vector<int> summits, int mid) {
    queue<int> q;
	memset(vi,0,sizeof(vi));
	for(int i=0;i<gates.size();++i) {
		q.push(gates[i]);
	}

	int summit = INF;

	while(!q.empty()) {
		int curr = q.front(); q.pop();

		if(summitCheck[curr]) {
			if(curr < summit) {
				summit = curr;
			}
			continue;
		}

		for(int i=0;i<adj[curr].size();++i) {
			int next = adj[curr][i].first;
			int time = adj[curr][i].second;

			if(!vi[next] && !gateCheck[next] && time <= mid) {
				vi[next] = 1;
				q.push(next);
			}
		}
	}

	if(summit == INF) return -1;
	else return summit;
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(int i=0;i<paths.size();++i) {
        int from,to,weight;
        from = paths[i][0];
        to = paths[i][1];
        weight = paths[i][2];
        
        adj[from].push_back({to,weight});
        adj[to].push_back({from,weight});
    }
    
    for(int i=0;i<summits.size();++i) {
		summitCheck[summits[i]] = 1;
	}
    for(int i=0;i<gates.size();++i) {
		gateCheck[gates[i]] = 1;
	}
    
    while(l+1<r) {
		int mid = (l+r)/2;

		int flag = false;
		int summit = bfs(gates, summits, mid);
		if(summit != -1) {
			flag = true;
			if(mid < ans[1]) {
				ans[0] = summit;
				ans[1] = mid;
			} else if(mid == ans[1]) {
				if(summit < ans[0]) {
					ans[0] = summit;
				}
			}
		}

		if(flag) {
			r = mid;
		} else {
			l = mid;
		}
	}

	if(ans[0] == INF && ans[1] == INF) {
		for(int i=0;i<gates.size();++i) {
			int summit = bfs(gates, summits, r);
			if(summit != -1) {
				ans[0] = summit;
				ans[1] = r;
			}
		}
	}
    
    return ans;
}

공식 카카오 해설

다익스트라를 응용하여 풀 수 있는 문제였다. 다익스트라 해설은 아래 카카오 해설을 참고하면 좋을 것 같다.
https://tech.kakao.com/2022/07/13/2022-coding-test-summer-internship/