프로그래머스 코딩테스트 그래프 01 - 가장 먼 노드
문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다.
1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.
노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
| n | vertex | return |
|---|---|---|
| 6 | [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] | 3 |
풀이
처음에는 간단하게 DFS를 이용하여 모든 노드에 접근 가능한 최소 길이를 구한 뒤 가장 멀리 있는 노드들의 개수를 구하는 방법으로 접근을 해보았다. 입출력 예제를 통과해서 채점을 해보았는데 시간초과에서 막히게 되었다.
- DFS 알고리즘 채점 결과
이유를 찾던 중 먼저 파이썬 ‘in’ 연산자에 대하여 자료형마다 시간 복잡도가 다르다는 것을 알게되었다. 파이썬 ‘in’ 연산자 시간 복잡도(Time Complexity)
따라서 모든 list 자료형 변수를 set으로 변경해주었다.
- 정점 탐색 여부 visited set() 으로 변경
- 딕셔너리 dic의 value인 이동 가능한 노드 정보 set() 으로 변경
하지만 문제는 해결되지 않았고 소요 시간이 유의미한 변화는 없었다.. 분명 인접리스트의 형태로 구현했고 자료형도 바꿔보았는데 해결이 안되서 매우 당황했다.
그래서 코드를 수정하여 BFS 알고리즘으로 구현하여 통과할 수 있었다.
BFS에서는 탐색 가능한 노드의 레벨(지나쳐온 간선의 길이) 최댓값을 리턴했다.
- BFS 알고리즘 채점 결과
코드(Python)
- DFS 알고리즘으로 구현한 코드 (시간 초과)
def dfs(dic, target, visited, v, path, shortest):
if v in visited or v == target:
shortest.append(path)
return
visited.add(v)
for vv in dic[v]:
if not vv in visited:
dfs(dic, target, set(visited), vv, path+1, shortest)
def solution(n, edge):
answer = []
dic = {}
for st, ed in edge:
dic.setdefault(st, set())
dic.setdefault(ed, set())
dic[st].add(ed)
dic[ed].add(st)
for i in range(1,n+1):
shortest=[]
dfs(dic, i, set(), 1, 0, shortest)
if len(shortest) > 0:
answer.append(min(shortest))
return answer.count(max(answer))
- queue를 이용한 BFS 알고리즘 코드
import collections
def bfs(dic, visited):
visited.add(1)
queue = collections.deque([1])
while queue:
path = len(queue)
for _ in range(path):
v = queue.popleft()
for vv in dic[v]:
if not vv in visited:
queue.append(vv)
visited.add(vv)
return path
def solution(n, edge):
dic = {}
for st, ed in edge:
dic.setdefault(st, set())
dic.setdefault(ed, set())
dic[st].add(ed)
dic[ed].add(st)
return bfs(dic, set())
댓글남기기