[프로그래머스] 가장 먼 노드 (python 파이썬)

문제

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

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

 

 

풀이 및 소스코드

자바랑 파이썬 같이 쓰려하니 넘 헷갈린다 ,,

ㅠ 

그치만 아직까진 파이썬이 조아 .....

 

bfs로 구현했다.

함수는 따로 만들지 않았다.

귀찮았다 ..

 

deque에 시작점(1)과 시작카운트(0) 을 담아서 while 문을 돌렸다.

q = ([1,0]) 이렇게 시작 !

1번 노드와 3번, 2번 노드가 연결되어있다고 했을 때,

q = ([3, 1])

q = ([3, 1], [2, 1])

위와 같이 q에 append가 된다.

q를 통해 2,3번 노드가 시작점에서 1만큼 거리가 있다는 것을 알 수 있다.

이 정보를 v 리스트에 넣어 방문 표시를 해주었다.

v[1] = 0

v[2] = 1

v[3] = 1

이렇게 방문 표시 겸, 거리 표시를 해주면 된다.

 

q가 비어서 while문이 끝났을 때,

v 리스트의 최댓값, 즉 시작점과 가장 먼 거리를 찾고, 그 값과 같은 노드들을 카운트 해주면 된다.

from collections import deque

def solution(n, edge):
    answer = 0
    node = [[]*(n+1) for _ in range(n+1)]
    for a, b in edge:
        node[a].append(b)
        node[b].append(a)
    v = [(-1) for _ in range(n+1)]
    q = deque([[1, 0]]) #시작, 카운트
    v[1] = 0
    while q:
        nowq, cnt = q.popleft()
        for i in node[nowq]:
            if (v[i]==-1):
                q.append([i, cnt+1])
                v[i] = cnt+1;
    mn = max(v)

    for i in v:
        if (i == mn):
            answer += 1

    return answer