백준 1260번 DFS, BFS

백준 1260번 DFS,  BFS

---

✏️ BOJ 1260

백준 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

---

백준 1260번 예제

 

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)

 

---

✏️ 참고한 영상

https://youtu.be/kkZFEwoZ3fA