BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이

📚  문제

원본: https://programmers.co.kr/learn/courses/30/lessons/49189?language=python3 

코딩테스트 연습 - 가장 먼 노드

💡 접근법

⚙️ 활용 알고리즘: BFS

 

저의 접근법은 다음과 같습니다.

2차원 리스트를 활용해 노드 간 연결정보를 업데이트하고 노드별 거리 정보를 저장할 1차원 리스트를 초기화합니다.

시작 노드를 큐에 삽입하고 해당 노드와 연결된 노드의 거리 정보를 시작 노드의 거리 정보에 1을 더해 업데이트합니다.

도착 노드를 다시 큐에 삽입하고 위의 과정을 반복합니다.

💻  My solution

from collections import deque

def solution(n, edge):
    answer = 0
    dist = [0]*(n+1)
    edge.sort()
    q = deque()
    graph = [[] for i in range(n+1)]
    
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
    q.append(1)
    dist[1] = 1
    
    while q:
        start = q.popleft()
        for end in graph[start]:
            if dist[end]==0:
                q.append(end)
                dist[end] = dist[start] + 1
        
    dist_max = max(dist)
    for d in dist:
        if d == dist_max:
            answer+=1     
            
    return answer

5, 8째 줄에서는 노드 번호를 그대로 인덱싱하기 위해 (n+1)개의 원소를 생성하였습니다.

6째 줄에서는 1번 노드부터 탐색을 시작하기 위해 edge를 오름차순 정렬하였습니다.

👀 참고할 만한 포스팅

이론 자료
1.  [알고리즘] 너비 우선 탐색(BFS) 알고리즘에 대해 알아보자!(+Python 구현)
2.  [알고리즘] 깊이 우선 탐색(DFS) 알고리즘에 대해 알아보자!(+Python 구현)
3.  [파이썬] map 함수에 대해 알아보자(Feat. lambda 표현식)
4.  [자료구조] 큐(Queue)에 대해 알아보자(+ Python)

관련 문제
1.  BFS 알고리즘 | 백준#11123 #실버 | "양 한 마리, 양 두 마리" | 파이썬 풀이
2.  BFS 알고리즘 | 백준#17086 #실버 | "아기상어2" | 파이썬 풀이
3.  DFS 알고리즘 #프로그래머스 #타겟넘버 | 파이썬 풀이
4.  BFS알고리즘 #프로그래머스 #가장 먼 노드 | 파이썬 풀이

---

문제 풀이 피드백이나 질문 환영합니다. 아래에 댓글 남겨주세요!👍

그럼 오늘도 건강하고 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.