# 1260번: DFS와 BFS

DFS 

def dfs( v, visited_dfs ):
  if not visited_dfs[v-1] :
    visited_dfs[v-1] = True
    print(v, end=' ')
    
    if v in graph.keys():
      for i in graph[v]:
          dfs( i, visited_dfs )

1. 시작 노드를 stack 에 넣고 방문 처리 

2. stack의 최 상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 stack 에 넣고 방문 처리 

   -> 최 상단 노드 중 방문하지 않은 인접 노드가 없으면 최상단 노드 pop 

3. 반복 

 

 

 

BFS 

def bfs( v, visited_bfs ) :
    queue = deque()
    queue.append(v)

    while queue : 
        now = queue.popleft()

        if not visited_bfs[now-1]:
          visited_bfs[now-1] = True
          print(now, end= ' ')

          if now in graph.keys():
            for i in graph[now]:
              queue.append(i)

1. 탐색 시작 노드를 큐에 넣고 방문 처리

2. 큐에서 노드를 꺼내어 해다 노드의 인접 노드 중 방문하지 않은 모든 노드를 큐에 삽입 하고 방문 처리

3. 반복 

 

 

 

실행 코드 

from collections import deque 

n, m, v = map(int,input().split()) # 노드, 간선, 시작점 

graph = dict()

for i in range(m):
    start, end = map(int,input().split())

    if start in graph:
        graph[start].append(end)
    else:
        graph[start] = [end] 

    if end in graph:
      graph[end].append(start)
    else:
      graph[end] = [start]

for i in graph.keys():
    graph[i].sort()

visited_dfs = [False] * n
visited_bfs = [False] * n  

dfs(v, visited_dfs)
print()
bfs(v, visited_bfs)

 

 

개념만 알면 풀 수 있는 문제일 줄 알았는데 생각보다 오래 걸렸다. 

그래프 만들 때, start-end 와 end-start  모두 넣어 주어야 하는 것에 유의하자. 

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS