프로그래머스 Level3 가장 먼 노드
백준으로만 그래프 문제를 풀다가 프로그래머스 환경에서 풀어본 첫 문제입니다.
정답 코드
from collections import deque
def solution(n, edge):
answer = 0
graph = [[] for _ in range(n + 1)]
for a, b in edge:
graph[a].append(b)
graph[b].append(a)
distance = [-1] * (n + 1)
queue = deque([1])
distance[1] = 0
while queue:
current = queue.popleft()
for i in graph[current]:
if distance[i] == -1:
queue.append(i)
distance[i] = distance[current] + 1
max_num = max(distance)
for i in distance:
if i == max_num:
answer += 1
return answer서론
백준에서는 값 입력부터 직접 작성해야해서 오히려 순조로웠다.
프로그래머스를 풀면서 당황한 점은 내가 직접 a, b 같은 입력 값을 받지않고 2차원 리스트와 n을 파라미터로 받아와서 사용했기 때문에 당황스러웠다.
bfs()를 여기 안에서 따로 또 만들어서 푸려고 진행을 하다가 사실상 밖에 입력하는 코드가 있는 것이라고 생각하고 solution 함수 자체를 bfs()라고 생각했다.
물론 위쪽에서 graph 변수를 정의해주거나 이러한 코드들은 원래 bfs() 안에 넣지 않지만 이런식으로 작성하였다.
문제를 보고 코딩테스트 연습에서 그래프 카테고리를 클릭해서 문제를 풀었기 때문에 그래프 문제인 것은 알았고 최단경로를 구해야한다고 하여서 BFS로 풀이를 진행하였다.
DFS로만 문제 풀이를 대부분 진행했기 때문에 BFS의 정형화된 코드를 한 번 보고 풀이하였다. (기억이 잘,,)
풀이과정
이제 서론은 생략하고 문제 풀이는
해당 문제에서의 이미지를 보고 직접 손으로 풀어보았다.
그 결과 노드 간선의 길이는 1: 0, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2가 나와야했기 때문에 간선의 길이를 세는 리스트를 만들어서 그 안에 [0, 0, 1, 1, 2, 2, 2] 이러한 꼴의 리스트를 뽑아내야한다고 생각했다.
edge로 주어진 리스트를 가지고 그래프를 만들어서 그 안에 각각 값들을 이어주었다.
그리고 간선의 길이를 저장할 리스트를 하나 생성한다.
여기서 주의할 점은 인덱스 0이 아니라 루트 노드 1번부터 시작할 것이기 때문에 전체적으로 n + 1로 범위를 잡는다.
그리고 distance는 -1 초기값으로 만들어준다.
그 후 첫 루트 노드 1은 0이기 때문에 인덱스 1은 0을 집어넣는다.
그리고 전형적인 bfs 풀이 코드를 작성한다. -1은 visited[False] 같은 느낌이라고 봐도 된다.
그리고 distance를 출력해보면
[-1, 0, 1, 1, 2, 2, 2] 이라는 리스트가 나오고 여기서 가장 큰 값을 뽑아낸 후 그 값과 일치하다면 answer +=1 하면 끝이다.
