[Python] 백준(BOJ) - 1260 DFS와 BFS (Dictionary)

이번 문제는 DFS와 BFS 기초이다.

그러나 정답률은 30.604%로 꽤나 저조한데... 그 자세한 이유는 실제로 풀어보면 알겠지만 생각보다 난해한 부분이 생긴다.

 

그러나 기초는 기초일 뿐.

Python3로 풀면 특히 쉽다.

보통은 Node로 그래프를 그려서 풀겠지만, 이번에는 Python의 Dictionary 자료형을 활용하여 해결해보았다.

 

한 번 바로 살펴보도록 하자.

---

소스 코드

#BOJ 1260 DFS와 BFS

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 node not in _graph:
                return visit
            for item in _graph[node]:
                s.append(item)
    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 node not in _graph:
                return visit
            q.extend(_graph[node])
    return visit
        
n, m, v = map(int, input().split())
graph = dict()
for _ in range(m):
    key, child = map(int, input().split())
    if key not in graph:
        graph[key] = list()
    if child not in graph:
        graph[child] = list()
    graph[key].append(child)
    graph[child].append(key)
    
for key in graph:
    graph[key].sort(reverse=True)
for item in dfs(graph, v):
    print(item, end=' ')
    
print()

for key in graph:
    graph[key].sort()
for item in bfs(graph, v):
    print(item, end=' ')

문제는 위에도 말했듯, 입력 받은 노드들로 그래프를 그릴 수 있고, DFS와 BFS의 기초를 묻는 질문이었다.

 

그러나 참 신기한 것이,

DFS를 출력할 때에는 Dictionary 자료형 안에 있는 Node의 자식들을 역순으로(내림차순으로) 정렬해야만 제대로 출력이 되었고,

BFS를 출력할 때에는 Dictionary 자료형 안에 있는 Node의 자식들을 정순으로(오름차순으로) 정렬해야만 제대로 출력이 되었다.

 

이 부분에 대해서는 왜 그런지 조금 더 고찰이 필요할 것 같다.

 

당연히 결과는 맞긴 맞았다. 그러나...

당연히 결과는 맞았습니다!! 이지만,

시간이 상당히 느리다.

332ms로, 1등의 경우 68ms이 걸렸고 꽤 많은 사람들이 70ms대에 있는 것을 알 수 있었다.

이 정도라면 Dictionary 자료형을 버리고 Node로 다시 짜는 게 나을 수 있다는 생각이 들었다.

 

P.S. 여담으로, 꼴등은 7448ms가 걸렸는데,

 

......이게 시간초과가 안 났다고?!

진심 다른 의미로 엄청나다.