99클럽 코테스터디 24일차 TIL 프로그래머스 - 가장 먼 노드

가장 먼 노드

프로그래머스 Level3 그래프

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

1번 노드로 부터 가장 먼 노드를 찾아서 해당 노드와 같은 거리 만큼 떨어져있는 노드의 갯수를 구하는 문제

문제 풀이

BFS 로 1번 부터의 거리를 각각 계산해주고, 거리를 계산해주면서, 해당 거리에 대한 arr 에다가 거리를 인덱스로 사용해 해당 인덱스에 몇개의 노드가 들어있는지 체크하는 형태로 풀이했다.


지금 생각해보니까 노드 간의 거리가 20002보다 길어질 수 있는데 별 생각없이 20002 로 했는데 풀렸다. 테케가 좀 약한듯

코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define MAXN 20002

using namespace std;

vector<vector<int>> gp(MAXN);
int dis[MAXN], res=0, record[MAXN] = {0, };

void bfs() {
    queue<int> q;
    q.push(1);
    dis[1] = 0;
    record[1] = 1;

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

        for (int i=0; i<gp[cur].size(); i++) {
            int next = gp[cur][i];
            if (dis[next] == -1) {
                dis[next] = dis[cur] + 1;
                q.push(next);
                res = max(res, dis[next]);
                record[dis[next]] += 1;
            }
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;

    gp.resize(n+1);
    for (int i=0; i<edge.size(); i++) {
        gp[edge[i][0]].push_back(edge[i][1]);
        gp[edge[i][1]].push_back(edge[i][0]);
    }

    fill(dis, dis+n+1, -1);

    bfs();

    return record[res];
}

 

회고

테케가 약한 문제는 SWEA 이후로 처음 찾았다고 생각했지만, 곰곰히 생각해보니 결국 노드의 갯수는 최대 20000 개로 제한되어 있기 떄문에 가중치가 없는 그래프에서 최대로 나올 수 있는 거리는 20001 정도이고 20002 로 하면 충분하네


문제가 쉽다고 넘겨짚으면 안되겠다.