[Python] 백준 1260번 : DFS와 BFS

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

 문제 풀이

DFS와 BFS 문제이다.

 

DFS와 BFS의 개념을 잡기 위한 문제인 것 같다.

DFS와 BFS를 구현해주면 된다.

 느낀 점

오랜만에 BFS, DFS를 풀어서 느낌을 다시 잡으려고 선택한 문제이다.

내가 기억하는 개념을 그대로 구현하려고 했는데 DFS가 좀 이상하다.. 웨지?..감자..?

deque 라이브러리를 사용하지 않고 구현하려고 했고, 딕셔너리를 이용해서 구현하려고 했다.

풀다가 중간에 keyerror가 계속 뜨길래 딕셔너리 문제였다 하하하!

 코드

import sys

def BFS(nodes, start):
    queue = [start]
    visisted = [start]
    
    while queue:
        n = queue.pop(0)
        print(n, end=' ')
        
        if n in nodes: 
            tmp = sorted(nodes[n])
            for node in tmp:
                if node not in visisted:
                    queue.append(node)
                    visisted.append(node)
                
def DFS(nodes, start):
    stack = [start]
    visited = []
    
    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            if n in nodes: stack += sorted(nodes[n], reverse=True)
    
    for v in visited:
        print(v, end=' ')
        
N, M, V = map(int, sys.stdin.readline().split())
nodes = {}
for _ in range(M):
    x, y = map(int, sys.stdin.readline().split())
    nodes[x] = nodes.get(x, []) + [y]
    nodes[y] = nodes.get(y, []) + [x]
    
DFS(nodes, V)
print()
BFS(nodes, V)