가장 먼 노드

날짜 : 2023. . 

사용 언어 : python

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49189

 

코드

from collections import deque
def solution(n, edge):
    queue = deque()
    graph = [[] for _ in range(n+1)]
    for s, e in edge:
        graph[s].append(e)
        graph[e].append(s)
    visited = [False] * (n + 1)  # 미방문 : False / 방문 : 방문거리
    visited[1] = 1  # 맨 처음 노드(0)
    queue.append(1)
    while queue:
        now = queue.popleft()  # 현재 노드
        for i in graph[now]:  # 현재 노드와 연결된 노드 탐색
            if visited[i] == False:  # 방문하지 않은 경우
                visited[i] = visited[now] + 1  # 방문처리(이동거리)
                queue.append(i)  # 추가
    m = max(visited)  # 이동거리가 최대
    res = 0
    for i in visited:
        if i == m:
            res += 1
    print(visited)
    return res

 

 

풀이

- 전형적인 BFS 문제였다.

- 각 간선마다 정보를 입력받은 후 방문처리를 해 나가면서 BFS를 진행한다.

- 이후 방문처리 리스트의 최대값(1에서 가장 먼 거리)을 구한 후 visited 리스트에서 값을 대조해 나가면서 개수를 가산한 후 값을 출력한다.

 

 

알게된 점

- 우선 visited 리스트의 값들을 전부 False로 초기화하다 보니 연산했을 때 False + int값이 나와 오류가 발생하는 케이스가 있었다. 해당 경우를 다행히 빠르게 캐치해서 답을 찾을 수 있었다.

- 그리고 False와 0이 동일하게 판별되는 것을 인지하지 못해서 이상한 값이 출력되었다. 이또한 빠르게 캐치할 수 있었다.

- 뭔가 사고력을 요구하는 프로그래머스 문제에서 전형적인 BFS 문제가 나오니까 신기했다.

 

 

참고 사이트

-