[Python] 백준(BOJ) - 1260 DFS와 BFS (인접 리스트)

이번에는 지난 번에도 풀었던 백준 1260번의 DFS와 BFS다.

지난 번에 파이썬의 딕셔너리 자료형으로 풀어서 332ms의 실행 시간이 나왔는데,

이번에는 전통적인 C/C++ 스타일로 인접 리스트를 만들어서 풀어보았다.

 

과연 결과는?

---

소스 코드

#BOJ 1260 DFS와 BFS - Adjecent Index

from collections import deque
import sys
input = sys.stdin.readline

def dfs(_graph, _start):
    visit = list()
    s = list()
    s.append(_start)
    while s:
        node = s.pop()
        if node not in visit:
            visit.append(node)
            if _graph[node] == None:
                return visit
            for i in range(len(_graph[node])-1, -1, -1):
                s.append(_graph[node][i])
    return visit

def bfs(_graph, _start):
    visit = list()
    q = deque()
    q.append(_start)
    while q:
        node = q.popleft()
        if node not in visit:
            visit.append(node)
            if _graph[node] == None:
                return visit
            q.extend(_graph[node])
    return visit
            
n, m, v = map(int, input().split())
graph = [list() for _ in range(n+1)]
for _ in range(m):
    key, child = map(int, input().split())
    graph[key].append(child)
    graph[child].append(key)

#DFS
for i in range(1, len(graph)):
    graph[i].sort()
for item in dfs(graph, v):
    print(item, end=' ')

print()

#BFS
for item in bfs(graph, v):
    print(item, end=' ')

과연 결과는...?

 

엥...?

어라...?

오히려 20ms 더 느려졌다...?

 

라고 하기에 생각해보면 파이썬의 딕셔너리 자료형은 너무나도 강력했다.

음.

다음 번엔 인접 행렬로 다시 도전해봐야겠다.