[그래프] 깊이/너비 우선 탐색(DFS/BFS)문제 3

문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

---

• 가중치 없는 edge의 최단거리 -> BFS 접근
• vertex 배열로 그래프 먼저 만들자
• 그 거리값을 가진 노드 개수 세기???
  • <GPT hint>
  • 거리 배열을 하나 만들어봐. -> distance = [-1] * (n + 1)
  • 시작 노드는 distance[1] = 0
  • BFS를 실행하며 아직 방문하지 않은 노드라면 -> distance[next] = distance[current] + 1

from collections import deque

def solution(n, edge):
    answer = 0
    far_edge = 0
    def bfs(start) :
        queue = deque([start])
        distance[start] = 0

        while queue :
            v = queue.popleft()
            for i in graph[v] :
                if distance[i] == -1 :
                    distance[i] = distance[v] + 1
                    queue.append(i)

    # graph = [[]]*(n+1) # 이렇게 하면 모든 칸이 같은 리스트 공유
    graph = [[] for _ in range(n + 1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)

    distance = [-1]*(n+1)
    bfs(1)
    # print(graph)
    # print(distance)
    # print(max(distance))
    for i in distance :
        if i == max(distance) :
            answer += 1
    # print(answer)

    return answer

# n = 6
# vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
# solution(n,vertex)

---

시행착오

#1 2차원 배열 빈 리스트 만들기

graph = [[]]*(n+1) # 이렇게 하면 모든 칸이 같은 리스트 공유

 

• 처음에 빈 리스트 배열 이렇게 만들었더니 append 하면 모든 리스트에 동일한 값이 할당됨
• 위와 같이 빈 리스트를 만들면 print 했을 때는 문제 없어 보이지만, 메모리 상에서는 동일한 1개의 빈 리스트 객체를 가리키는 꼴이 되어버림
• 따라서 서로 다른 객체의 빈 리스트 원소를 여러개 생성할 때는 아래와 같이 for문을 활용

graph = [[] for _ in range(n + 1)]

---

#2 distance 리스트를 왜 bfs의 매개변수로 넣어주지 않아도 bfs 함수 내에서 에러가 안생기는지?

Python의 클로저(Closure) 와 LEGB 규칙 때문.

Python은 변수를 찾을 때 아래 순서로 탐색함.

현재 함수(Local) → 바깥 함수(Enclosing) → 전역(Global) → 내장(Built-in)

 

따라서 bfs() 내부에 distance가 없더라도, 바깥 함수인 solution()의 distance를 찾아 사용할 수 있음.

 

또한 BFS 내부에서 수행하는

distance[i] = distance[v] + 1

은 distance 변수를 새로 만드는 것이 아니라 리스트 객체 내부의 값만 수정하는 것.

그래서 nonlocal 선언도 필요하지 않음.

 

반면,

distance = [0, -1, -1]

이와 같이 distance 자체를 새로 할당/정의하면 Python은 이를 bfs()의 지역 변수로 판단함.

이 경우 바깥 함수의 distance와는 다른 변수가 되며, 상황에 따라 UnboundLocalError가 발생할 수 있음.