# 1260 DFS와 BFS

문제 : <https://www.acmicpc.net/problem/1260>

```python
import sys
input = sys.stdin.readline

N, M, V = map(int, input().split())

# 그래프를 표현하는 인접 리스트
graph = [
    [],         # 0번 노드는 사용하지 않음 (노드 번호를 1부터 맞추기 위해)
    [2, 3, 4],  # 1번 노드와 연결된 노드들
    [1],        # 2번 노드와 연결된 노드들
    [1, 5],     # 3번 노드와 연결된 노드들
    [1],        # 4번 노드와 연결된 노드들
    [3]         # 5번 노드와 연결된 노드들
]

graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for node in graph:
    node.sort()

# print(graph)

# 깊이 우선 탐색 DFS
# 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
# 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면
#    그 인접 노드를 스택에 넣고 방문 처리를 한다.
#    그리고 방문하지 않은 인접 노드가 없으면 최상단 노드를 꺼낸다
# 3. 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

def dfs(node, visited):
    visited.append(node)
    print(node, end=' ')
    if len(graph[node]) == 0:
        return
    for near in graph[node]:
        if near not in visited:
            dfs(near, visited)

visited = []

dfs(V,visited)
print('')
# print('dfs 완료')

# 너비 우선 탐색 BFS
# 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
# 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서
#    방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
# 3. 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

from collections import deque

def bfs(node, visited, waiting):
    visited.append(node)
    waiting.append(node)
    while len(waiting) != 0:
        node = waiting.popleft()
        print(node, end=' ')
        for near in graph[node]:
            if near not in visited:
                waiting.append(near)
                visited.append(near)
    return

visited = []
waiting = deque()

bfs(V,visited, waiting)
# print('bfs 완료')
```

BFS와 DFS를 구현해보면 되기만 하는 간단한 문제.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/1260-dfs-bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.