[백준 1260번] DFS와 BFS

 

# 화가난다... 정답 제출 형식을 제대로 파악하지 못해 2시간을 날렸다...

# 계속 리스트 형식으로 제출했는데 구글링을 하고 보니 정답 제출 형식이 str ㅋㅋ....

# 2시간동안 dictionary를 잘못만든건지 DFS와 BFS 알고리즘을 잘못 짠건지만 고민했다 ㅠ

 

-- 정답 코드

 

import sys
from collections import deque

# 정점의 개수 N
# 간선의 개수 M
# 탐색을 시작할 정점의 번호 V
N, M, V = map(int, input().split())

gansun = {}

for _ in range(M):
    a, b = map(int,sys.stdin.readline().split())
    if a in gansun:
        gansun[a].add(b)
    else:
        gansun[a] = set([b])
    if b in gansun:
        gansun[b].add(a)
    else:
        gansun[b] = set([a])

def DFS(graph, root):
    visited = []
    stack = deque([root])
    while stack:
        n = stack.pop()
        if n not in visited: # 아직 방문 안했다면 추가
            visited.append(n)
            temp = list(graph.get(n,set()) - set(visited))
            temp.sort(reverse = True) # LIFO 구조를 만들기 위해 역순으로 넣어준다
            stack += temp
    return [str(i) for i in visited]

def BFS(graph, root):
    visited = []
    queue = deque([root])
    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            temp = list(graph.get(n, set()) - set(visited))
            temp.sort(reverse=False) # 인접한 노드가 작은 순으로 방문
            queue += temp
    return [str(i) for i in visited]

print(" ".join(DFS(gansun, V)))
print(" ".join(BFS(gansun, V)))

 

TIL에서 공부했던 DFS, BFS 코드를 활용해 코드를 만들었다. 코드가 완벽히 같지 않은 이유는 2시간동안 어떤 부분이 문제일지 고민하며 이곳저곳을 모두 건드려 봤기 때문이다.

 

 

 

오늘은 DFS와 BFS 알고리즘을 성공적으로 복습하였다.