분류
그래프 이론(graphs), 그래프 탐색(graph_traversal), 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs)
문제 설명
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
4 5 1
1 2
1 3
1 4
2 4
3 4
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
1 2 4 3
1 2 3 4
아이디어
이코테 강의 중 DFS/BFS 개념 정리할 때 예제 구현과 동일하다!
dfs는 스택 + 재귀, bfs는 큐를 이용하는데 bfs 코드는 한 번에 생각이 안 나서 정리해둔 글 살짝 확인하면서 풀었음
→ 시간 조금 지나고 다시 풀어볼 예정
내 코드
from collections import deque
def dfs(graph, now, visited):
visited[now] = True
print(now, end=' ')
for node in graph[now]:
if not visited[node]:
dfs(graph, node, visited)
def bfs(graph, start, visited):
q = deque([start])
visited[start] = True
while q:
now = q.popleft()
print(now, end=' ')
for node in graph[now]:
if not visited[node]:
q.append(node)
visited[node] = True
# __main__
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited_d = [False] * (n+1)
visited_b = [False] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(n+1):
graph[i].sort()
dfs(graph, v, visited_d)
print()
bfs(graph, v, visited_b)다른 사람 코드에서 참고할 만한 부분
나는 각 함수에서 바로 노드를 출력하도록 구현했는데, 방문한 순서를 리스트로 받고 배열을 출력하는 방식도 가능함
방문한 노드 숫자를 받을 리스트를 dfs_list(bfs_list)라고 한다면
print(now, end=' ') → dfs_list.append(now) 로 수정 가능
출력 시 print(*dfs_list) 와 같이 리스트 앞에 *을 붙여주면 리스트 자체가 아니라 리스트 내 원소가 각각 출력됨
list = [1, 2, 3, 4] print(list) # [1, 2, 3, 4] print(*list) # 1 2 3 4
