💡코딩테스트/프로그래머스
[프로그래머스 | 파이썬 python] 가장 먼 노드
두_두
2023. 5. 20. 23:52
그래프 | BFS
🌏 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
👽 풀이 ➡️ BFS 이용
from collections import deque
def solution(n, edge):
edges = [[] for _ in range(n + 1)]
graph = [0 for _ in range(n+1)]
visited= [0 for _ in range(n+1)]
def bfs(n):
queue = deque()
queue.append(n)
visited[n] = 1
while queue:
n = queue.popleft()
for i in edges[n]:
if visited[i] == 0:
graph[i] = graph[n] + 1
visited[i] = 1
queue.append(i)
for e in edge:
a, b = e
edges[a].append(b)
edges[b].append(a)
bfs(1)
return graph.count(max(graph))
728x90