(Python/LV3)가장 먼 노드

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

풀이:

from collections import deque
def solution(n, edge):
    dist = [1] + [0] * (n - 1)
    graph = [[ ] for i in range(n)]
    q =deque([1])
    for x, y in edge:
        graph[x-1].append(y)
        graph[y-1].append(x)
    while q:
        l = len(q)
        for i in range(l):
            now = q.popleft()
            for e in graph[now-1]:
                if dist[e-1] == 0:
                    dist[e-1] = 1
                    q.append(e)
    return l

dist 는 밟았을 경우 1로 만들어주기 위해 0으로 만들어주고 시작지점은 이미 밟았으니 1을 해준다.

graph = 그래프

q 에 시작지점 1을 넣어줌

 

edge를 돌면서 graph 간선들을 추가해준다.

graph = [[3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]] 이런식으로 나온다

 

리스트를 보면 1이랑 연결된건 [3.2] / 2랑 연결된간 [1,3,4,5] 이런식으로 된거를 그래프로 만들어준다.

 

q를 이용하여

l 을 len(q) 를 넣는다. 

for 문을 돌면서 현재 위치를 뽑아준다.그러면 시작인 now 는 1 

graph[1 -1] 0 번째 노드 >> 1번이랑 연결된것들을 포문돈다.

그러면 [3, 2] 추출된다. dist[2],dist[1] 은 0 이므로 1로 바꿔주고 밟았으니깐 q에 3이랑 2 추가

 

다음 while문 돌면

q 에는 [2,3] 이 들어있고, dist = [1,1,1,0,0,0] 이렇게 바뀌었을것이다.

똑같이 포문 돌면서

2랑 연결된거 체크하고, 3이랑 연결된거 체크한다.

그러면 [6,4,5] 가 들어있다.  q가 비었으니 저 길이만큼 리턴