문제

풀이

입력값으로 리스트를 만들고 dfs(재귀), bfs(큐)를 이용해 풀었다.

BFS (Breadth-First-Search)

• 너비우선탐색이라 부른다

과정

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

예시 코드

from collections import deque

# 노드의 연결정보를 표현
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7]
]

#각 노드가 방문된 정보를 표현
visited = [False]*9

#구현
def bfs(graph, start, visited):
  queue=deque([start])
  #현재노드 방문처리
  visited[start]=True
  #큐가 빌때까지 반복
  while queue:
    #큐에서 하나의 원소를 뽑아 출력
    v=queue.popleft()
    print(v, end=' ')
    #아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True

bfs(graph, 1, visited)

코드

# 1260 DFS와 BFS

from collections import deque
n, m, v = map(int, input().split())
graph = [[0]*(n+1) for _ in range(n+1)]
visited_dfs = [0]*(n+1)
visited_bfs = [0]*(n+1)

for i in range(m):
  a, b = map(int, input().split())
  graph[a][b] = graph[b][a] = 1

def dfs(v):
  visited_dfs[v] = 1
  print(v, end=' ')
  for i in range(1,n+1):
    if(visited_dfs[i] == 0 and graph[v][i] == 1):
      dfs(i)

def bfs(v):
  queue = deque([v])
  visited_bfs[v] = 1
  
  while queue:
    v = queue.popleft()
    print(v,end=' ')
    for i in range(1, n+1):
      if(visited_bfs[i] == 0 and graph[v][i] == 1):
        queue.append(i)
        visited_bfs[i] = 1

dfs(v)
print()
bfs(v)

결과