문제
https://school.programmers.co.kr/learn/courses/30/lessons/49189
주요 아이디어
1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return하는 문제이다.
- BFS를 통해 인접 노드를 탐색
- distance 배열을 통해서 노드 1과의 거리가 얼마인지를 저장
- 이 때 시작점은 1번 노드 고정이므로 1차원 배열로 커버 가능하다
코드 구현 (Python 3)
더보기
from collections import deque
def solution(n, edge):
graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
for s, e in edge:
graph[s].append(e)
graph[e].append(s)
for idx in range(len(graph)):
graph[idx].sort()
# 초기값 설정
queue = deque();
queue.append(1)
distance[1] = 1
while queue:
cur = queue.popleft()
for adj in graph[cur]:
if distance[adj] == 0:
queue.append(adj)
distance[adj] = distance[cur] + 1
return len([x for x in distance if x == max(distance)])
제출 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 징검다리 건너기 (0) | 2024.05.21 |
---|---|
[프로그래머스] 문자열 다루기 기본 (0) | 2024.05.21 |
[프로그래머스] 단어 변환 (0) | 2024.04.11 |
[프로그래머스] 행렬 테두리 회전하기 (0) | 2024.04.11 |
[프로그래머스] 등굣길 (0) | 2024.04.08 |