[프로그래머스 level3] 가장 먼 노드

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

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

해결방안

• BFS 알고리즘

알고리즘

1. 1에서 출발하여 각 거리에 있는 노드들을 고려하기 위한 딕셔너리 생성 (result_list)

2. vertex를 그래프로 만들기 위한 딕셔너리 생성 (graph)
3. edge를 돌면서 graph에 양방향 그래프 초기화
4. 중복 방문을 방지하기 위해 방문여부를 처리하는 배열 생성 (visited)
5. BFS 수행
   1. 1번노드를 큐에 넣고 방문처리, 시작점이므로 cnt는 0으로 초기화
   2. 큐에서 노드를 뽑아서, 방문안한 노드일 경우에만 방문처리하고 큐에 넣기
      1. 각 노드까지의 거리를 나타내는 result_list에 key값으로 현재 cnt에 +1을 설정하고 value로 현재의 노드번호 넣기
      2. 나중에 result_list돌면서 가장 먼 거리에 있는 노드들 얻기 위함
   3. 2번을 반복
6. result_list를 n을 키로 가진것부터 0번째까지 역순으로 반복하며 key 값이 가장 클때의 리스트의 길이를 리턴

핵심 팁

• 문제를 이해하는 것이 중요
  • 기본적인 BFS, DFS 문제
• DFS로 풀어도 가능
  • BFS로 푸는것이 구현하기에 좀 더 쉬울것으로 예상했음

 

Python

from collections import deque
from collections import defaultdict
def solution(n, edge):
    ans = 0
    result_list = defaultdict(list)
    graph = defaultdict(list)
    for data in edge:
        a, b = data
        graph[a].append(b)
        graph[b].append(a)
    visited = [False] * (n + 1)
    def bfs(start):
        q = deque([(start, 0)])
        visited[start] = True
        while q:
            now, cnt = q.popleft()
            for i in graph[now]:
                if visited[i] is False:
                    visited[i] = True
                    q.append((i, cnt + 1))
                    result_list[cnt + 1].append(i)
    bfs(1)
    for i in range(n, -1, -1):
        if i in result_list and len(result_list[i]) > 0:
            ans = len(result_list[i])
            break
    return ans

n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
ans = solution(n, vertex)
print(ans)

 

*퍼가신다면 출처와 댓글 부탁드립니다.

*더 많은 자료는 아래 github에 있습니다

https://github.com/griffinGC/Algoritm_PS

https://github.com/griffinGC/TIL_Public