프로그래머스: 가장 먼 노드⭐⭐⭐

난이도 ⭐⭐⭐
유형 : 자료구조

🧐 문제

문제 설명

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

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

제한사항

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

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

접기/펼치기

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

---

🔍 힌트

이번 문제는 BFS를 사용하여, 깊이 값이 가장 큰 노드들의 개수를 구하면 되는 문제입니다.

이 그래프의 깊이 값들은,

깊이	노드 번호
0	1
1	3,2
2	6,4,5

라고 할 수 있습니다. (본인은, 깊이를 0부터 세었음)

이제 여기서 가장 깊은 깊이인, 2에 해당하는 노드의 개수를 카운트하면 됩니다.

---

✏️ 나의 풀이

#include <bits/stdc++.h>

using namespace std;

// 간선 정보
vector<int> edges[20001];
// 방문 정보
vector<bool> visited(20001);

int bfs(int root) {
    // 큐 선언 후, 루트를 넣어주고 방문 처리
    queue<pair<int, int>> q;
    q.push(make_pair(root, 0));
    visited[root] = true;

    int max_depth = 0;
    int cnt = 0;
    while(!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        // 더 깊은 노드가 존재한다면, 다시 카운트
        if(max_depth < cur.second) {
            max_depth = cur.second;
            cnt = 0;
        }
        cnt++;

        // 연결된 노드들 방문
        for(int edge : edges[cur.first]) {
            if(visited[edge]) continue;
            visited[edge] = true;
            // 새 노드의 깊이 = 현재 노드 깊이 + 1
            q.push(make_pair(edge, cur.second + 1));
        }
    }

    return cnt;
  
}

void init(vector<vector<int>>& input_edges) {
    for(auto edge : input_edges) {
        edges[edge[0]].push_back(edge[1]);
        edges[edge[1]].push_back(edge[0]);
    }
}

int solution(int n, vector<vector<int>> input_edges) {
    init(input_edges);
    return bfs(1);
}

✔️ 다른 사람의 풀이

from collections import deque

def solution(n, edge):
    answer = 0
    # 연결된 노드 정보 그래프
    graph =[[] for _ in range(n+1)]
    # 각 노드의 최단거리 리스트
    distance = [-1] * (n+1)
    
    # 연결된 노드 정보 추가
    for e in edge :
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])  
    
    
    queue = deque([1]) # BFS를 위한 queue, 출발 노드 = 1
    distance[1]=0 # 출발노드의 최단거리를 0으로
    
    # BFS 수행
    while queue :
        now = queue.popleft() # 현재 노드
        
        # 현재 노드에서 이동할 수 있는 모든 노드 확인
        for i in graph[now]:
            if distance[i] == -1: # 아직 방문하지 않은 노드면,
                queue.append(i) # queue에 추가
                distance[i] = distance[now] + 1 # 최단거리 갱신
    # 가장 멀리 떨어진 노드 개수 구하기
    for d in distance:
        if d == max(distance):
            answer += 1
    return answer

🧐 분석

1. 앞뒤로 원소를 관리할수 있는 deque를 사용하고 있다.
2. 나의 코드와는 다르게, 깊이 값들을 distance 배열을 통해 모두 저장해두고 있다.
3. 루프를 돌며 가장 깊은 노드들을 카운트하고 있다.
4. 나의 코드가 최적화에 더 좋다.

Programmers 카테고리 내 다른 글 보러가기