사용 언어 - Python3
문제 - 가장 먼 노드
https://school.programmers.co.kr/learn/courses/30/lessons/49189
정답
구현
연결된 노드를 모두 확인해주면서 max(거리)인 경우를 카운트하기
1. 연결된 노드 정보를 저장해준다.
예) graph[1번노드] = 3번 노드 , grpah[3번 노드] = 1번 노드
2. 각 노드를 기준으로 최단거리를 저장할 distance 리스트를 생성한다.
거리는 0 일수도 있으니 디폴트값을 -1로 설정한다.
distance = [-1] * (n+1)
3. 1번노드에서 출발
queue = deque([1])
distance[1] = 0
최단거리는 0으로 설정해준다.
4. BFS 수행
현재 노드 now 에서 이동할 수 있는 모든 노드를 방문한다.
방문하지 않았던 노드 즉, distance가 디폴트값인 -1인 경우만 방문하면서
최단거리를 갱신한다. distance[i] = 현재까지의 distance + 1
5. 가장 멀리 떨어진 노드 개수를 구한다.
distance 들 중에 max(distance)인 경우 answer += 1
from collections import deque
def solution(n, edge):
answer = 0
# 연결된 노드 정보 그래프
graph = [[] for _ in range(n+1)]
# 각 노드의 최단거리 리스트. 거리는 0일수도 있으니 -1을 디폴트값으로 설정
distance = [-1] * (n+1)
# 연결된 노드 정보 추가. 양방향 연결
for e in edge :
graph[e[0]].append(e[1])
graph[e[1]].append(e[0])
# BFS를 위한 queue, 출발 노드 = 1
queue = deque([1])
# 출발노드의 최단거리를 0으로
distance[1] = 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
레퍼런스
- 깃허브 정답
'Algorithm > DFS&BFS&백트래킹&재귀' 카테고리의 다른 글
[프로그래머스 lv 3] PCCP 기출 4번 수레 움직이기 (1) | 2023.12.11 |
---|---|
[프로그래머스 lv 3] 순위 (1) | 2023.12.08 |
[프로그래머스 lv 2] PCCP 기출 2번 석유 시추 (1) | 2023.12.06 |
[백준] 1197번 최소 스패닝 트리 (프림, 크루스칼) (0) | 2023.11.08 |
[백준] 1717번 집합의 표현 (유니온 파인드 문제) (1) | 2023.11.06 |
댓글