Coding test(Python3)/BaeckJoon
[BOJ 1260번] DFS와 BFS
녜잉
2024. 8. 3. 00:39
1. 문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
2. 문제 풀이
인접 리스트를 선언하여 각 그래프의 연결 정보를 저장한다(안그러면 순서 엉망됨)
DFS 문제 풀이
- dfs함수에 graph, start, visited, order(연결 그래프, 시작 노드, 방문 여부, 순서 리스트)를 매개변수로 전달한다.
- 시작 노드의 방문 여부를 true로 변경하고, order 리스트에 노드를 추가한다.
- 인접 리스트에 저장되어 있는 연결 노드 정보를 기반으로, 노드의 방문 여부를 확인한다.
- 만약 인접한 노드에 방문한 적이 없다면, 해당 노드와 인접한 다른 노드의 정보를 수집하기 위해 재귀함수를 호출하여 연결 그래프를 탐색한다.
BFS 문제 풀이
- 시작 지점을 미리 넣어둔 큐를 정의하고, 현재 노드의 방문 여부를 true로 변경한다.
- 큐에 노드가 없을 동안 반복한다.
- 큐의 가장 첫번째 원소를 pop하고, 해당 원소를 order 리스트에 추가한다.
- 현재 노드와 인접한 노드의 방문 여부를 확인한다.
- 만약 방문하지 않은 노드가 있다면 해당 노드의 방문 여부를 true로 변경하고 노드의 연결 정보를 확인하기 위해 큐에 추가한다.
- order 리스트를 반환한다
import sys
from collections import deque
def dfs(node, start, visited, order):
visited[start] = True
order.append(start)
for neighbor in sorted(node[start]):
if not visited[neighbor]:
dfs(node, neighbor, visited, order)
def bfs(node, start, visited):
queue = deque([start])
order = []
visited[start] = True
while queue:
current = queue.popleft()
order.append(current)
for neighbor in sorted(node[current]):
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return order
N, M, V = list(map(int, sys.stdin.readline().split()))
graph = {i: [] for i in range(1, N+1)}
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
order = []
visited = [False] * (N+1)
dfs(graph, V, visited, order)
print(' '.join(map(str, order)))
visited = [False] * (N+1)
print(' '.join(map(str, bfs(graph, V, visited))))
완전 전형적인 dfs / bfs 문제였다~~
안푼지 너무 오래 되어서 재활할려고 문제 풀어봄 프로그래머스 전력망 나누기 문제랑 비슷했다(아무래도 그래프를 dfs로 탐방한다는 점에서..)
dfs 문제는 그래도 보면 딱 감잡고 대충이라도 구현할 줄 알겠는데 아직도 bfs는 애매한 느낌..더 많이 풀어봐야할듯?
그리고 백준 골드 됨 ㅎㅋㅎㅋ
더 열심히 할게요..