[프로그래머스] 등산코스 정하기 - 2022 카카오 인턴십

파닥몬·2022년 9월 23일
0

KAKAO를 풉니다.

목록 보기
11/12
post-thumbnail

⚙️ 알고리즘 분류 : 다익스트라

🔠 언어 : c++

🤫 힌트.

다익스트라의 시작점이 여러 개인 경우다.

✏️ 풀이.

문제 풀이 단계
1) 준비 - 산봉우리인 번호를 배열에 체크한다. 그리고 path가 양방향이므로, 이를 vector로 만든 배열에 저장한다.

2) 각 출발점을 하나씩 다익스트라 함수의 인자로 넘긴다.

3) 기본적인 다익스트라 함수로 구현하되, dist 값을 바꾸는 조건을 바꾼다.
➡️ (보통) dist[next]>now_cost+next_cost
(해당 문제) dist[next]>max(now_cost, next_cost)

3-1) 만약 next가 산봉우리라면 멈춰야 하기 때문에 priority_queue에 넣지 않는다.

4) 산봉우리를 하나씩 돌면서 가장 작은 dist 값을 갖는 산봉우리를 찾는다.

⚠️ 헤맨 부분.

다익스트라 문제의 대부분은 출발지에서 도착지까지 거치는 모든 path의 가중치를 합 중 최소를 구하는 문제다.
이번 문제는 다익스트라 알고리즘을 변형시켜서 풀어야 했다.
도착지까지 거치는 모든 path의 가중치 중 가장 큰 값을 구하고, 그 값 중 가장 작은 값을 구해야 했다. 그래서 해당 알고리즘을 생각하는 부분이 어려웠다.

처음에는 '도착지에 도달했을 경우'를 따로 예외 상황으로 뺐다. 근데 코드가 더러웠고, 무엇보다 답이 안 구해졌다. 그래서 다익스트라 함수 내 값들을 출력했다. 2가지 문제가 발생했고, 이를 해결하다보니 알고리즘을 구할 수 있었다.

(1) 모든 path의 가중치 중 가장 작은 값이 구해졌음.
➡️ 가장 핵심적인 부분이다. 이를 구하기 위해서 현재 방문한 node(=now)와 그 다음에 방문할 후보 node(=next)의 각 cost 중 최댓값을 구했다.
=> max(now_cost, next_cost)
그리고 최댓값과 next의 dist 값 중 최솟값을 다시 next의 dist로 넣었다.
=> min(cost 최댓값, dist[next])

(2) 도착지(산봉우리) 도달 이후에도 연결된 다른 node로 이동됨.
➡️ 그냥 산봉우리 도착하면 next를 priority_queue에 안 넣으면 됐다.

👩🏻‍💻 코드.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#define mp make_pair
#define MX 999999999
using namespace std;
priority_queue<pair<int,int>> pq;
vector<pair<int,int>> v[50001];
vector<int> dist(50001, MX);
int ch_summit[50001];

void dij(int start){
    dist[start]=0;
    pq.push(mp(0, start));
    while(!pq.empty()){
        int now=pq.top().second;
        int cost=-pq.top().first;
        pq.pop();
        
        for(int i=0; i<v[now].size(); i++){
            int next=v[now][i].first, next_cost=v[now][i].second;
            // max(현재 node의 cost, 다음에 방문할 node의 cost)
            int mx_cost=max(cost, next_cost);
            // dist: 해당 node에 도달하면 발생하는 특정(최대 or 최소) cost 저장
            // dist에는 최소값을 저장
            if(dist[next]>mx_cost){
                dist[next]=mx_cost;
                // 만약 다음에 방문할 node가 산봉우리라면, 안 넣는다.
                if(!ch_summit[next]) pq.push(mp(-dist[next], next));
            }
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer(2, MX);
    // 산봉우리인 거 체크
    for(int i=0; i<summits.size(); i++) ch_summit[summits[i]]=1;
    for(int k=0; k<paths.size(); k++){
        int i=paths[k][0], j=paths[k][1], w=paths[k][2];
        v[i].push_back(mp(j,w));
        v[j].push_back(mp(i,w));
    }
    // 각 출발점마다 알고리즘을 돌린다.
    for(int i=0; i<gates.size(); i++) dij(gates[i]);
    for(int i=0; i<summits.size(); i++){
        int summit=summits[i];
        if(answer[1]>=dist[summit]){
            // dist가 같은 경우엔 산봉우리 숫자가 더 작은 것
            answer[0]=(answer[1]==dist[summit]) ? min(answer[0], summit) : summit;
            answer[1]=dist[summit];
        }
    }
    return answer;
}

예전에 1번 푼 적이 있다. 그 땐 카카오에서 보여준 풀이를 보고 따라 푼 것이다.
=> 2022 KAKAO TECH INTERNSHIP 코테 풀이

카카오 풀이에선 다익스트라의 모든 시작점의 dist를 0으로 초기화 하라고 했다.
즉, 다익스트라의 시작점이 여러개일 경우, 한 번에 0으로 초기화 하는 것이다.
위의 문제에 적용하여 풀어봤다.

딱 2개 부분에서 바꿨다!
(1) 함수 dij에서 인자를 삭제. dist[start]=0, pq에 입력하는 부분 삭제
(2) gates의 값을 하나씩 보며 dist[gates[i]]=0, pq에 입력하는 부분 추가.

#include <string>
#include <vector>
...

void dij(){
    while(!pq.empty()){
        int now=pq.top().second;
        int cost=-pq.top().first;
        pq.pop();
        
        ....
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer(2, MX);
    // 산봉우리인 거 체크
    ...
    
    for(int i=0; i<gates.size(); i++) {
        // 한 번에 초기화 && 입력
        dist[gates[i]]=0;
        pq.push(mp(0, gates[i]));
    }
    dij();
    ...
    return answer;
}

😎 후기.

2022 카카오 인턴에 지원했었다. 당시 마지막까지 잡고 있던 문제였는데, 테스트케이스 한 2개인가 못맞춰서 결국 떨어졌다.
다시 풀어보니까 '이거 다익스트라로 풀어야겠는데?' 싶은 생각을 했지만, 당시엔 이걸 dfs+dp로 풀려고 했다. 확신하고 풀었는데, 왜 확신했는지 모르겠다ㅎㅎ
이번에 2번째 푸는 거라서 이전에 풀었던 기억이 조금 남아있었다.
실제 시험에서 생각해내는 게 중요한데...

profile
파닥파닥

0개의 댓글