DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는

정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 

 

· 입력 

첫째 줄에 정점의 개수 N(1<= N <= 1,000), 간선의 개수 (1<= M <= 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의

줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 

양방향이다.

 

· 출력

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

 

· 입출력 예 

input	output
4 5 1 1 2 1 3 1 4 2 4 3 4	1 2 4 3 1 2 3 4
5 5 3 5 4 5 2 1 2 3 4 3 1	3 1 2 5 4 3 1 4 2 5
1000 1 1000 999 1000	1000 999 1000 999

---

풀이

1. Me

import collections 

def solution(dict_graph: dict, v: int):
    graph = dict_graph
    def dfs(v: int, discovered = []) -> list:
        discovered.append(v)
        for w in graph[v]:
            if w not in discovered:
                discoverd = dfs(w, discovered)
        return ' '.join(map(str, discovered))

    def bfs(v: int) -> str:
        discovered = [v]
        queue = [v] 
        while queue:
            v = queue.pop(0)
            for w in graph[v]:
                if w not in discovered:
                    discovered.append(w)
                    queue.append(w)
        return ' '.join(map(str, discovered))

    dfs_list = dfs(v, [])
    print(dfs_list)
    bfs_list = bfs(v)
    print(bfs_list)

# 입력 값을 입력받고, 그래프 생성 
n, m, v = map(int, input().split())
graph = collections.defaultdict(list)

count = 0
while True:
    if count == m:
        break
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)
    count += 1 

# 정점 번호가 낮은 순으로 출력해야 하기 때문에, 정렬한다.
for i in graph:
    graph[i].sort()
solution(graph, v)

dfs의 경우 재귀함수를 통해 문제를 풀었고, bfs의 경우 재귀함수를 통한 문제 풀이가 불가능하기 때문에 큐를 이용하여 문제를 풀었다. 코드를 좀 더 다듬을 수 있을거 같으니, 여러 방식으로 풀어보자.