BOJ 1260

Input

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

N, M, V = map(int, input().split())
visited = [False for _ in range(N+1)]
graph = [[0]*(N+1) for _ in range(N+1)] # for 문이 아니라 *로 초기화
for _ in range(M):
  s, e = map(int, input().split())
  graph[s][e] = graph[e][s] = 1 # 한 줄로 동일값 넣기

DFS

• 들어오는 대로 바로바로 처리 (먼저 깊게 들어가고 다시 올라와 옆으로)

• LIFO = 스택

# 밑으로 방문 후 pop
def dfs(V):
  # end 조건이 없어도 되는 이유
  # for 1~N 까지 돌면서, 남은 요소 중 조건을 만족하는 게 없으면 끝남

  visited[V] = True
  print(V, end=" ")
  for i in range(1, N+1):
    if graph[V][i] == 1 and not visited[i]:
      dfs(i)

BFS

• 같은 레벨 전부, 그 다음 밑으로
• FIFO = 큐

# 옆으로 방문하며 append
# 이전 V의 자식들 방문
def bfs(V):

  # dfs와 동일한 배열을 사용하므로, True/False 번갈아가며...
  visited[V] = False
  queue = [V]

  while queue:
    V = queue.pop(0)
    print(V, end=" ")
    i = 1

    for i in range(1, N+1):
      if graph[V][i] == 1 and visited[i]:
        visited[i] = False
        queue.append(i)

Output

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.

dfs(V)
print()
bfs(V)