문제 이해
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
예제
입력
4 5 1
1 2
1 3
1 4
2 4
3 4
출력
1 2 4 3
1 2 3 4
1과 2, 3, 4가 연결되어 있고, 2와 4가 연결되어 있고, 3과 4가 연결되어 있다.
DFS에 따르면 깊이 우선 탐색이고 같은 깊이라면 낮은 번호가 우선순위이므로 1 다음 2에 접근하고 2와 4가 연결되어 있으므로 4를 방문한다. 3과 4가 연결되어 있으므로 다음은 3을 방문하여 총 1, 2, 4, 3의 결과가 나오게 된다.
BFS에 따르면 너비 우선 탐색이므로 1다음 2를 방문하고 같은 선상에 있는 3을 방문, 다음으로 4를 방문하는 형식이다.
문제 접근
현재의 node와 방문했다는 표시, 다음 node를 찾는 방식으로 나눌 수 있겠다.
보통 DFS는 stack과 재귀함수를 사용하여 구현을 많이 한다. 따라서 재귀함수를 사용하여 DFS를 구현하려 했다.
BFS는 queue를 사용하여 구현한다. 파이썬에는 내장된 deque가 있기 때문에 이를 사용하여 queue를 나타내고 BFS를 구현한다.
문제 풀이
시작 전 처리
아래와 같이 2차원 배열에 간선을 표현해주었다.
각각의 배열엔 연결되어 있는 노드가 들어가 있다.
또한 문제에서 주어진 조건에서 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다고 했기 때문에 sort()를 통해 정렬해준 후에 DFS, BFS를 실행한다.
arr = [[] for _ in range(N+1)]
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
arr[a].append(b)
arr[b].append(a)
for i in arr:
i.sort()DFS
현재의 node를 node라 하고 다음 노드를 next_node라 했다.
현재의 node를 방문했다는 표시를 한 후에 arr[node], 즉, node에 연결된 다른 정점들 중에 방문한 적이 없는 next_node를 찾아서 dfs(next_node)를 통해 재귀호출 해준다.
def dfs(node):
visited[node] = True
print(node,end=" ")
for next_node in arr[node]:
if visited[next_node] == False:
dfs(next_node)
BFS
queue에 node를 초기값으로 넣는다.
초기 노드에 방문 표시를 한다.
queue가 다 비워질 때까지 반복하는데, 현재의 node를 node에 저장하고, arr[node]를 탐색하면서 방문한 적이 없는 next_node를 발견하면 이를 방문 표시하고 queue에 append해준다.
def bfs(node):
queue = deque([node])
visited[node]=True
while queue:
node = queue.popleft()
print(node, end=" ")
for next_node in arr[node]:
if visited[next_node] == False:
visited[next_node] = True
queue.append(next_node)제출 코드
import sys
from collections import deque
N,M,V = map(int, sys.stdin.readline().split())
arr = [[] for _ in range(N+1)]
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
arr[a].append(b)
arr[b].append(a)
for i in arr:
i.sort()
def dfs(node):
visited[node] = True
print(node,end=" ")
for next_node in arr[node]:
if visited[next_node] == False:
dfs(next_node)
def bfs(node):
queue = deque([node])
visited[node]=True
while queue:
node = queue.popleft()
print(node, end=" ")
for next_node in arr[node]:
if visited[next_node] == False:
visited[next_node] = True
queue.append(next_node)
visited = [False for _ in range(N+1) ]
dfs(V)
print()
visited = [False for _ in range(N+1)]
bfs(V)
# dfs stack or 재귀
# bfs queue