코딩테스트 연습 '가장 먼 노드' 문제 풀이

코딩테스트 연습 '가장 먼 노드' 문제 풀이

문제

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

주어진 간선 정보를 인접리스트로 만든 후 bfs를 수행하여 방문할 때마다 count+=1을 하는 방식으로 쉽게 해결 가능한 문제입니다.

이해하기 쉽게 문제에서 주어진 예시로 설명해 보겠습니다.

노드 개수 6개

간선 정보: [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

graph

문제를 해결하기 위해 거리와 방문처리를 동시에 나타낼 수 있게 -1*(n+1)로 이루어진 리스트를 하나만듭니다.

[-1, -1, -1, -1, -1, -1, -1] 각각의 인덱스는 노드 번호를 가르키며 -1은 방문처리가 되지 않은 노드입니다.

-1이 아닌 0으로 초기화하게 되면 거리가 1씩 증가된 상태로 카운트하게 됩니다.

BFS를 마치면 방문리스트에는 [-1, 0, 1, 1, 2, 2, 2]가 저장되고 문제에서 요구하는 것은 가장 멀리 떨어진 노드의 개수이므로 최대값 2의 개수를 반환하면 예시에 대한 답인 3이 나옵니다.

문제 풀이

from collections import deque def solution(n, edge): graph=[[] for _ in range(n+1)] visited=[-1]*(n+1) for a,b in edge: graph[a].append(b) graph[b].append(a) queue=deque([1]) #1번 노드부터 방문 visited[1]=0 while queue: v=queue.popleft() for i in graph[v]: if visited[i]==-1: queue.append(i) visited[i]=visited[v]+1 return visited.count(max(visited))

from http://lbdiaryl.tistory.com/224 by ccl(A) rewrite - 2021-12-07 16:26:48