728x90
백준 1260번 DFS, BFS
✏️ BOJ 1260
✏️ DFS : 하나의 노드만 몰아서 본다. 몰아서 탐색!
1. start_node를 방문, visited 배열에 방문 기록 남기기
2. start_node의 인접 노드 방문(current_node), visited배열에 방문 기록 남기기
3. 인접노드의 방문 기록이 있거나, 인접노드가 없으면 직전 노드로 돌아간다.
4. 모든 노드를 방문했다면, 더 이상 방문할 노드가 없으므로 탐색 종료
def dfs(c): # current node
ans_dfs.append(c) # 방문 노드 추가
visited[c] = 1 # 방문 표시
for n in adj[c]:
if not visited[n]: # 방문하지 않은 노드의 경우
dfs(n)
✏️ BFS : 여러 인접 노드를 한번씩 살펴본다.
1. start_node를 방문, visited 배열에 방문 기록 남기기
2. start_node의 인접 노드을 queue(FIFO)에다 저장.
3. queue가 빈 상태가 될 때까지 queue에 저장된 인접노드 순으로 방문.
4. queue가 비어었으면, 더 이상 방문할 노드가 없으므로 탐색 종료
def bfs(s):
q = [] # 필요한 q, visited[], 변수 생성
q.append(s) # 초기 시작 데이터 삽입
ans_bfs.append(s)
visited[s] = 1 # start
while q:
c = q.pop(0)
for n in adj[c]:
if not visited[n]: # next node가 방문하지 않은 노드라면, 큐 삽입
q.append(n)
ans_bfs.append(n)
visited[n] = 1
def dfs(c): # current node
ans_dfs.append(c) # 방문 노드 추가
visited[c] = 1 # 방문 표시
for n in adj[c]:
if not visited[n]: # 방문하지 않은 노드의 경우
dfs(n)
def bfs(s):
q = [] # 필요한 q, v[], 변수 생성
q.append(s) # 초기 시작 데이터 삽입
ans_bfs.append(s)
visited[s] = 1 #start
while q:
c = q.pop(0)
for n in adj[c]:
if not visited[n]: # next node가 방문하지 않은 노드라면, 큐 삽입
q.append(n)
ans_bfs.append(n)
visited[n] = 1
import sys
N, M, V = map(int, sys.stdin.readline().rstrip().split())
adj = [[] for _ in range(N+1)] # 서로 인접한 노드 양방향 기록.
for _ in range(M):
n1, n2 = map(int, sys.stdin.readline().rstrip().split())
adj[n1].append(n2)
adj[n2].append(n1) # 양방향
for li in adj:
li.sort() # 정점 번호가 작은 것을 먼저 방문한다고 했으니, 오름차순 정렬
visited = [0]*(N+1)
ans_dfs = []
dfs(V)
visited = [0]*(N+1)
ans_bfs = []
bfs(V)
print(*ans_dfs)
print(*ans_bfs)
✏️ 참고한 영상
'알고리즘' 카테고리의 다른 글
재귀함수, 하노이의 탑 (0) | 2023.03.07 |
---|---|
DFS 관련 연산 문제 (0) | 2023.03.07 |
데일리 알고리즘 230120 (0) | 2023.01.22 |
데일리 알고리즘 230119 (0) | 2023.01.19 |
데일리 알고리즘 230118 (0) | 2023.01.18 |