프로그래머스 _ 가장 먼 노드

https://programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

1. 풀이 방법

 

이 문제는 정확성 테스트밖에 없으므로 크게 시간에 구애받지않고 풀어도 되어 두가지 방법으로 풀어보았다.

 

1) 무식하게 dfs돌려서 나온 그 노드의 최단거리와 노드값을 모두 한 벡터에 몰아두고, 마지막에 거리의 오름차순 정렬시켜 정답 출력하기 ( O(V+ E) ) ?

 

2) 다익스트라를 써서 최단경로를 구하고, 마지막에 최단거리 배열값에 있는 값중에 가장 먼 노드들 찾아 출력하기

( O(E*logV) ) ? 맞나?

 

두 방법다 더럽게 오래걸린다. 더 나은 방법이 있는지 생각해봤는데 잘 모르겠다.

 

---

 

2. 코드

 

1) 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

bool visit[20001];
vector<vector<int>> node(20001);
//거리, node 저장
vector<pair<int, int>> result;
//nodeidx, cnt 저장
queue<pair<int, int>> nextBfs;

void bfs(int nodeidx, int cnt)
{
    result.push_back({ cnt, nodeidx });

    for (int i = 0; i < (int)node[nodeidx].size(); i++)
    {
        int nextnode = node[nodeidx][i];
        int nextcnt = cnt + 1;

        if (visit[nextnode] == false)
        {
            visit[nextnode] = true;
            nextBfs.push({ nextnode, nextcnt });
        }
    }

    if (!nextBfs.empty())
    {
        int nextnode = nextBfs.front().first;
        int nextcnt = nextBfs.front().second;
        nextBfs.pop();
        bfs(nextnode, nextcnt);
    }

}

bool compare(pair<int, int>a, pair<int, int> b)
{
    return a.first > b.first;
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    visit[1] = true;

    for (int i = 0; i < (int)edge.size(); i++)
    {
        int firstNode = edge[i][0];
        int secondNode = edge[i][1];

        node[firstNode].push_back(secondNode);
        node[secondNode].push_back(firstNode);
    }

    bfs(1, 0);

    sort(begin(result), end(result), compare);

    int cnt = 0;
    int maxdistance = result[0].first;
    for (auto& ele : result)
    {
        if (maxdistance != ele.first)
            break;
        cnt++;
    }

    return cnt;
}

 

2)풀이

#include <string>
#include <vector>
#include <algorithm>
#include <queue>

#define INF 987654321

using namespace std;

vector<int>dist;
vector<vector<int>> gedge;
priority_queue<pair<int, int>> pri_que;
int maxdistance;

void distInit(int n)
{
    dist.resize(n + 3);
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
}

void dijstra(int here, int distance)
{
    for (int i = 0; i < (int)gedge[here].size(); i++)
    {
        int there = gedge[here][i];
        int nextdis = distance + 1;

        if (dist[there] > nextdis)
        {
            dist[there] = nextdis;
            pri_que.push({ -nextdis, there });
            maxdistance = max(maxdistance, dist[there]);
        }
    }

    if (!pri_que.empty())
    {
        int there = pri_que.top().second;
        int nextdis = -pri_que.top().first;
        pri_que.pop();
        dijstra(there, nextdis);
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    distInit(n);
    gedge.resize(n + 2);
    for (int i = 0; i < edge.size(); i++)
    {
        int s, e;
        s = edge[i][0];
        e = edge[i][1];

        gedge[s].push_back(e);
        gedge[e].push_back(s);
    }

    dijstra(1, 0);

    for (int i = 1; i <= n; i++)
        if (dist[i] == maxdistance)
            answer++;

    return answer;
}

 

---

 

3. 후기

그냥 다익스트라 복습할겸 두가지 형태로 짜봤는데 최단경로를 구하며 가중치가 1일때는 그냥 편하게 DFS로 풀자 ㅋㅋ