[프로그래머스] 가장 먼 노드

문제 요약

그래프 정보가 vertex 개수, 엣지들로 주어집니다.
1번 노드에서 가장 먼 노드까지의 거리를 구하세요

아이디어

전형적인 1:n 거리구하기 문제이다.
기준점 노드도 항상 1번으로 박혀있으며 vertex 이름도 1-n으로 고정되어있다.

삽질

큐에서 하나씩 빼주며 이미 dist 값이 결정된 노드면 continue를 해줘야한다.
근데 이걸 일반적으로 if(dist[cur.v]<cur.d) continue;로 구현하는데 이렇게 했을 때 값이 같으면 cur를 기준으로 똑같은 다익스트라를 한 번 더 돌게 된다. 일반적으론 이렇게 해도 웬만한 큐사이즈에선 통과되는 걸로 알고 있긴 한데 이 때문에 몇몇 테케에서 시간초과, 메모리 초과가 있었다.
다익스트라는 이 노드를 처음 방문할 때 (큐에 넣을 때 말고 뺄 때) 이 노드가 가질 수 있는 거리 후보 중 최솟값이라는 걸 이용해서 if(dist[cur.v]!=INF) continue;로 바꿔주었다.

코드

#include <string>
#include <vector>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//다익스트라로 1:n 거리를 구해보자!
int INF = 2*10000+1;
int dist[20001];
vector<vector<int> > g;//0번인덱스는 놀게
struct ca{
    int v, d;
    ca(int vv, int dd){
        v = vv; d=dd;
    }
};
struct comp{
    bool operator() (ca &a, ca &b){
        return a.d>b.d;
    }
};

void dijk(){
    priority_queue<ca, vector<ca>, comp> q;
    ca cur = ca(1, 0);
    q.push(cur);
    
    while(!q.empty()){
        cur = q.top();
        q.pop();
        
        if(cur.d>=dist[cur.v]){//한번 거쳐갔거나
            //cout<<"skipping "<<cur.v <<" "<<cur.d<<" "<<dist[cur.v]<<endl;
            continue;
        }
        dist[cur.v] = cur.d;
        for(int i = 0;i<g[cur.v].size();i++){
            int c = g[cur.v][i];
            if(dist[cur.v]+1<dist[c]){
                q.push(ca(c, dist[cur.v]+1));
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    g.push_back(vector<int>());
    for(int i = 0;i<n;i++){
        g.push_back(vector<int>());
    }
    for(int i = 0;i<edge.size();i++){
        int a = edge[i][0],b = edge[i][1];
        g[a].push_back(b);
        g[b].push_back(a);
    }
    //init dist
    for(int i = 0;i<=n;i++){
        dist[i] =INF;
    }
    int m= 0;
    dijk();
    for(int i = 0;i<=n;i++){
        //cout<<dist[i]<<" ";
        if(dist[i] !=INF){
            m = max(m, dist[i]);
        }
    }
    for(int i = 0;i<=n;i++){
        if(dist[i] == m) answer++;
    }
    return answer;
}

잡담

사실 나는 중고딩때만해도 극악의 문과성향이었다. 가장 좋아하는 과목은 영어, 두번째로 좋아하는 과목은 국어...수학은 가장 자신 없는 과목이었는데 과학 공부가 멋져보여서 이과를 선택했다.(내신으론 과학 학력우수상 많이 탔는데 수능 땐 수학 공부한다고 과학을 포기하다시피 해서 다 까먹고 물 화 둘 다 4등급 받았다 ㅋㅋ.ㅋ.ㅋ.ㅋ.) 학교 과학의 날 행사 같은거 있으면 자신있게 글쓰기를 선택했던 기억도 있는데 근데 고등학교 2년 대학 4년을 이과충으로 살다보니 4학년 2학기를 맞아 이제 문과 교양 달랑 하나 듣고 있는데 어쩜 이렇게 글을 못 쓰는지.... 능력이라는 게 안 쓰면 퇴화되고 쓰면 증진되는 게 맞나보다... 나에게 글 쓰기가 힘들어서 코딩 문제를 푸는 게 쉬는 걸로 느껴지는 날이 올줄은 몰랐다. 심지어 블로그 글도 ㅎ.. 썩 잘 쓰지 않아......