99클럽 코테 스터디 15일차 TIL 프로그래머스 가장 먼 노드

잡설

어제는 사실 챌린저 문제로 방의 개수라는 그래프 문제가 나왔다.

권장시간이 4시간이기도 했지만, 요즘 너무 바쁜 일정에 PS하듯 고민할 시간이 없어 일단 TIL은 제출하고, 추후에 곰곰히 고민해서 공부할 예정이다. 무작정 1시간 고민하고 답을 보는건 지금 별로 좋지 않은것 같다..

일단 점이 이동하면서 다시 만나면 도형이 생성된다는 것까지는 생각해보았으나.. 시간문제로 미들러 문제인 가장 먼 노드르 대체한다.

 

프로그래머스 가장 먼 노드

나는 이 문제를 힙을 사용한 다익스트라를 활용해서 풀었다.

시작이 노드1로 고정되어있기 떄문에 모든 정점까지의 거리를 구한뒤 최대 크기를 구하면 되는 간단한 문제였다.

나의 코드

def solution(n, edge):
    import heapq
    graph=[[] for _ in range(n)]
    dist=[1e8 for _ in range(n)]
    for s,e in edge:
        graph[s-1].append(e-1)
        graph[e-1].append(s-1)
    que=[]
    dist[0]=0
    heapq.heappush(que,[0,0])
    while que:
        now,far=heapq.heappop(que)
        if dist[now]>far:
            continue
        for nt in graph[now]:
            if dist[nt]!=1e8:
                if dist[nt]>dist[now]+1:
                    dist[nt]=dist[now]+1
                    heapq.heappush(que,[nt,dist[nt]])
            else:
                dist[nt]=dist[now]+1
                heapq.heappush(que,[nt,dist[nt]])
    c=max(dist)
    answer=dist.count(c)
    return answer