Page tree

Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

  • 문제 : 백준 1260. DFS와 BFS

    Code Block
    languagepy
    title풀이
    linenumberstrue
    collapsetrue
    import sys
    input = sys.stdin.readline
    from collections import deque
    
    def dfs(graph, v):
        visited = {}
        stack = [v]
    
        while stack:
            n = stack.pop()
            if n not in visited:
                visited.setdefault(n)
                stack += reversed(graph[n])
        return visited
    
    def bfs(graph, v):
        visited = {}
        queue = deque([v])
        
        while queue:
            n = queue.popleft()
            if n not in visited:
                visited.setdefault(n)
                queue += graph[n]
        return visited
    
    n, m, v = map(int, input().split())
    
    graph = {i:[] for i in range(1,n+1)}
    for i in range(1, m+1):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)
    
    for key in graph:
        graph[key].sort()
    
    print(' '.join(list(map(str,dfs(graph, v)))))
    print(' '.join(list(map(str,bfs(graph, v)))))
    
    
    
    dfs : stack 이므로 reverse해서 넣어주고 위에서부터 꺼냄
    bfs : queue 이므로 그대로 큐에 넣어줌
    
    두개의 collection을 연결하는 경우 extend보다 +=이 더 빠르다고 함. (https://stackoverflow.com/questions/4176980/is-extend-faster-than)
    setdefault(n) : 키값만 넣은 것. 해당키가 없으면 저장
    
    

    출처: https://ebbnflow.tistory.com/236


...