모눈종이에 사각사각
[백준 260] DFS와 BFS 본문
🍎 [백준 1260] DFS와 BFS
⚾ 코드
from collections import deque
# 정점의 개수 N(1 ≤ N ≤ 1,000)
# 간선의 개수 M(1 ≤ M ≤ 10,000)
# 탐색을 시작할 정점의 번호 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)
# 인접 리스트를 사용할 것이기 때문에 정렬이 필요함.
for i in range(N+1):
graph[i].sort()
# dfs 구현
def dfs(node):
if visited[node] == False:
# 아직 방문하지 않았을 경우
visited[node] = True
# 방문 기록 해주고
print(node, end=" ")
# 인접한 노드에서 다시 dfs 호출
for i in range(len(graph[node])):
dfs(graph[node][i])
# bfs를 위한 deque
q = deque()
def bfs(node):
if visited[node] == True:
# 아직 방문하지 않았을 경우
# dfs를 먼저 구현했기 때문에 visited는 True로 초기화 되어 있을 것
# 따라서 True가 방문하지 않았을 경우이다.
visited[node] = False
# 방문 기록을 해준 후
q.append(node)
# q에 삽입해준다.
print(node, end=" ")
while q:
# q가 비었을 때 까지 반복
x = q.popleft()
# 맨 앞에서 하나 꺼낸 후 인접한 모든 노드들을 방문하고 q에 append
for i in graph[x]:
if visited[i] == True:
visited[i] = False
print(i, end=" ")
q.append(i)
dfs(V)
print()
bfs(V)
🔔 해결과정 & 깨달은 점
- dfs와 bfs의 기본 아이디어를 구현해보았다.
- 양방향 간선일 경우 양쪽에 다 추가해 주어야 한다.
- 인접 리스트의 경우 정렬을 해주어야 가장 숫자가 작은 노드부터 방문할 수 있었다.
- dfs는 이제 잘 구현하는 것 같은데, bfs를 작성할 때 시간이 조금 걸렸다. bfs도 익숙해 질 수 있도록 노력하자.
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준 2294] 동전2 (0) | 2022.02.20 |
---|---|
[백준 11727] 2×n 타일링 2 (0) | 2022.02.20 |
[백준 7569] 토마토 (0) | 2022.02.18 |
[백준 7576] 토마토 (0) | 2022.02.17 |
[백준 2178] 미로 탐색 (0) | 2022.02.17 |
Comments