[백준 1260] DFS와 BFS

0. 제목

• 백준 1260 DFS와 BFS
• BOJ 1260 DFS와 BFS
• Python 1260 DFS와 BFS

---

1. 문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

---

2. 풀이

• dfs의 경우 인접한 정점들을 차례로 탐색할 수 있도록 재귀를 사용한다.
• bfs의 경우 deque를 사용한다. 탐색을 마치면 pop을 하고 인접한 정점 중 방문하지 않았던 점은 append로 deque에 추가해줌으로써 deque가 빌 때까지 반복하여 수행한다.
• 방문여부를 나타내는 배열은 각 탐색을 시작하기 전에 False로 초기화를 시켜준다.

---

3. 코드

from collections import deque
 
def dfs(v):
    print(v, end=' ')
    visited[v] = True
    for e in adj[v]:
        if not(visited[e]):
            dfs(e)
            
def bfs(v):
    q = deque([v])
    while q:
        v = q.popleft()
        if not(visited[v]):
            visited[v] = True
            print(v, end=' ')
            for e in adj[v]:
                if not visited[e]:
                    q.append(e)
                    
n, m, v = map(int, input().split())
adj = [[] for _ in range(n + 1)]
 
for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)
    
for e in adj:
    e.sort()
    
visited = [False] * (n + 1)
dfs(v)
print()
visited = [False] * (n + 1)
bfs(v)