[백준_그래프] DFS와 BFS

문제

 

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

 

 

입력

 

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

출력

 

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

 

 

예제 입력

 

4 5 1
1 2
1 3
1 4
2 4
3 4

 

 

예제 출력

 

1 2 4 3
1 2 3 4

 

 

 

 

 풀이

 

주어진 문제는 그래프에서 DFS와 BFS를 이용하여 정점들을 탐색하고, 탐색한 결과를 출력하는 것입니다. 

 

각각의 알고리즘에 대한 접근 방식은 다음과 같습니다.

1. DFS (깊이 우선 탐색):
   - 시작 정점 V에서 출발하여 가능한 한 깊숙히 들어가면서 정점을 탐색합니다.
   - 방문한 정점은 방문했다고 표시하고, 이어진 정점들 중 방문하지 않은 정점을 스택에 넣어 계속해서 깊게 탐색합니다.
   - 스택에 더 이상 탐색할 정점이 없으면 이전 단계로 돌아가면서 탐색을 진행합니다.

2. BFS (너비 우선 탐색):
   - 시작 정점 V에서 출발하여 가능한 한 넓게 주변 정점을 탐색합니다.
   - 방문한 정점은 방문했다고 표시하고, 이어진 정점들 중 방문하지 않은 정점을 큐에 넣어 순서대로 탐색합니다.
   - 큐에 더 이상 탐색할 정점이 없으면 주변 정점들 중에서 탐색을 진행합니다.

주어진 문제에서는 DFS와 BFS를 이용하여 시작 정점 V부터 탐색을 시작하고, 각 정점을 방문 순서대로 출력해야 합니다. 

 

따라서 아래와 같은 접근 방식을 사용합니다.

 

1. 그래프 정보를 인접 리스트로 저장합니다. 간선 정보를 입력받을 때 양방향으로 연결되어 있으므로, 양쪽 정점을 서로에게 추가합니다.

2. DFS 함수를 정의하고, 시작 정점 V에서 출발하여 깊이 우선 탐색을 수행합니다. 스택을 사용하여 정점을 탐색하며 방문한 정점을 출력합니다.

3. BFS 함수를 정의하고, 시작 정점 V에서 출발하여 너비 우선 탐색을 수행합니다. 큐를 사용하여 정점을 탐색하며 방문한 정점을 출력합니다.

4. DFS와 BFS 함수를 호출하고, 방문한 정점을 출력하면서 문제에서 요구하는 순서대로 출력합니다.

 

 

이러한 방식으로 주어진 그래프를 탐색하면서 DFS와 BFS의 결과를 출력할 수 있습니다.

 

 

 

소스 코드

from collections import deque

# 그래프 정점의 개수 N, 간선의 개수 M, 시작 정점의 번호 V 입력 받기
N, M, V = map(int, input().split())

# 그래프 초기화
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

# 간선 정보 입력 받기
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# DFS 함수 정의
def dfs(v):
    visited[v] = True
    print(v, end=' ')
    for neighbor in sorted(graph[v]):
        if not visited[neighbor]:
            dfs(neighbor)

# BFS 함수 정의
def bfs(start):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in sorted(graph[v]):
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

# DFS 수행 및 결과 출력
dfs(V)
print()

# BFS 수행 및 결과 출력
visited = [False] * (N+1)  # BFS를 위해 visited 초기화
bfs(V)