[BOJ 1260] DFS와 BFS - Python 풀이

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

코드

import sys
from collections import defaultdict
from collections import deque

def BFS(n, m, v, graph, queue):
    visited = [v]
    queue.append(v)

    while queue:    
        v = queue.popleft()
    
        if v in graph.keys():
            for w in graph[v]:
                if w in visited:
                    continue
                visited.append(w)
                queue.append(w)
    
    return visited

def DFS(n, m, v, graph, visited):
    visited.append(v)

    if v in graph.keys():
        for w in graph[v]:
            if w in visited:
                continue
            DFS(n, m, w, graph, visited)
    
    return visited

if __name__ == "__main__":
    n, m, v = map(int, sys.stdin.readline().split())
    graph = defaultdict(list)

    for _ in range(m):
        frm, to  = map(int, sys.stdin.readline().split())
        graph[frm].append(to)
        graph[to].append(frm)

    ## 정렬
    list_of_graph = sorted(graph.items(), key = lambda x: x[1])
    graph = dict(list_of_graph)
    [value.sort() for _, value in graph.items()]

    print(" ".join(map(str, DFS(n,m,v,graph,[]))))
    print(" ".join(map(str, BFS(n,m,v,graph,deque()))))

 

결과

풀이

DFS랑 BFS를 잘 못해서 호석님의 그래프 탐색 문제집을 풀어보기로 했다.(링크 참고)

생각보다 내가 DFS BFS를 잘 모른다는 것을 알았다;; 이제라도 알았음 됐지 뭐ㅎ

DFS와 BFS의 가장 큰 차이는 DFS의 경우 재귀 함수 구조라는 것이고 BFS는 queue(여기서는 deque)를 이용한다는 것이다.

다른 것은 다 괜찮았는데 무작위로 받아지는 간선과 정점을 정렬하는 것, 88% 쯤에서 간선이 이어져 있지 않은 정점 때문에 런타임 에러를 찾는 것 이 두 개 때문에 약간 시간이 지체됐다. 이 링크가 도움이 많이 됐다.