[파이썬, Java] 가장 먼 노드

문제 설명

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번 노드입니다.

 

👻 나의 풀이

 

from collections import deque

def solution(n, vertex):
    answer = []  # 가장 멀리 떨어진 노드의 개수
    graph = {}
    visited = [0] * (n + 1)

    for i in range(1, n + 1):
        graph[i] = list()

    for i, j in vertex:
        graph[i].append(j)
        graph[j].append(i)

    def bfs():
        que = deque([[1, 0]])
        while que:
            node, cnt = que.popleft()
            if not visited[node] :
                visited[node] = 1
                answer.append([node, cnt])
                for i in graph[node]:
                    if not visited[i]:
                        que.append([i, cnt + 1])

    bfs()

    cnt=0
    _max=max(answer, key=lambda x:x[1])[1]
    for a in answer :
        if a[1] == _max :
            cnt+=1

    return cnt

 

bfs 문제다.

마지막에 가장 먼 노드의 거리, 갯수를 구하는 부분이 지저분한 것 같아서 조금 아쉽다..

visited에 노드의 거리를 넣었으면 깔끔했을텐데😥

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;     // 거리
        ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<n+1; i++){
            graph.add(new ArrayList());
        }
        for (int[] node : edge){    // 노드 연결정보
            graph.get(node[0]).add(node[1]);
            graph.get(node[1]).add(node[0]);
        }
        
        Queue<Integer> que=new LinkedList();
        int[] visited=new int[n+1];   // 방문기록
        que.add(1);
        visited[1]=1;
        int node=0;
        int max_cnt=0;
        while(!que.isEmpty()){
            node=que.poll();
            for(int value:graph.get(node)){
                if(visited[value] == 0){
                    que.add(value);
                    visited[value]=visited[node]+1;
                    if (visited[value] > max_cnt){
                        max_cnt=visited[value];
                    }
                    }
            }  
        }
        for(int i=1; i<n+1; i++){
            if(visited[i] == max_cnt){
                answer++;
            }
        }
       return answer; 
    }
}

 

다른 사람 풀이를 보고 이해한 뒤 다시 짜본 코드

 

 

 

🎑 다른 사람 풀이

 

# 출처 : https://velog.io/@devjuun_s/%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4python
from collections import deque

def bfs(v, visited, adj) :
    count=0
    q=deque([[v, count]])
    
    while q :
        value=q.popleft()
        v=value[0]
        count=value[1]
        if visited[v] == -1 :	# 방문 안 했으면
            visited[v] =count
            count+=1
            # adj[v]와 연결된 노드에
            for e in adj[v] : 
                q.append([e, count])
                
def solution(n, edge):  # 노드의 개수, 간선 정보
    answer = 0
    visited=[-1]*(n+1)	# 1번부터 사용
    adj=[[] for _ in range(n+1)]
    
    for e in edge :
        x=e[0]
        y=e[1]
        # 양방향 연결
        adj[x].append(y)
        adj[y].append(x)
    bfs(1, visited, adj)
    
    for value in visited :
        if value == max(visited) :
            answer+=1
    return answer

 

deque와 bfs를 이용해서 구현.

방문한 노드가 아니면 visited[v]에 count를 넣는다.

노드 v와 연결된 노드들을 q에 추가한다.

visited에서 가장 큰 값을 구하고 갯수를 센다.

최단거리를 구할 때 bfs를 주로 사용(dfs와 구별되는 점)

 

 

# 출처 : https://donis-note.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B0%80%EC%9E%A5-%EB%A8%BC-%EB%85%B8%EB%93%9C-level-3-python-%ED%92%80%EC%9D%B4-248455cfa49d
import collections

def solution(n, vertex):
    dists={i:0 for i in range(1, n+1)}
    edge=collections.defaultdict(list)	# 딕셔너리로 변환
    
    # 양방향 표현
    for v, u in vertex :
        edge[v].append(u)
        edge[u].append(v)
    
    q=collections.deque(edge[1])
    dist=1
    
    while q :
        for i in range(len(q)) :
            v=q.popleft()
            
            if dists[v] == 0 :
                dists[v]=dist
                # 연결된 노드들 큐에 추가
                for w in edge[v] :
                    q.append(w)
        dist+=1
    
    del dists[1]
    
    max_value=max(dists.values())
    
    answer=0
    for v in dists.values() :
        if v == max_value :
            answer+=1

    return answer

 

딕셔너리, deque, bfs 이용

dists는 노드 1번과 i번의 거리를 저장하는 딕셔너리

 

 

 

 

출처 💁‍♀️ 프로그래머스