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

🔑 오늘의 학습 키워드 : 그래프

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

from collections import deque

def solution(n, edge):
    answer = [0] * (n+1)
    graph = {i:[] for i in range (1,n+1)}
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
    queue = deque([(1,0)])
    visited = set([1])
    while queue:
        node,distance = queue.popleft()
        for next_node in graph[node]:
            if not next_node in visited:
                queue.append((next_node,distance+1))
                visited.add(next_node)
                if graph[next_node]:
                    answer[next_node] = distance+1
    
    return answer.count(max(answer))

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

그래프 문제인데 가중치 없고 거리가 1이므로 그냥 bfs하면서 탐색하면 될 것 같다

 

⏰ 예상 시간 복잡도 O(V+E)

제한 사항

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

😎 알고리즘 개요

1. graph 변수에 간선들의 정보를 저장해준다.

    graph = {i:[] for i in range (1,n+1)}
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)

2. queue에 현재 노드와 거리를 담고 탐색해나간다.

    queue = deque([(1,0)])
    visited = set([1])
    while queue:
        node,distance = queue.popleft()
        for next_node in graph[node]:
            if not next_node in visited:
                queue.append((next_node,distance+1))
                visited.add(next_node)
                # leaf node
                if graph[next_node]:
                    answer[next_node] = distance+1

3. 가장 큰 숫자를 찾고 얼마나 나왔는지 return한다.

    return answer.count(max(answer))

✅ 오늘의 회고

-  이전에 푼 문제도 싹 지우고 다시 푸니까 재밌다

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL