[백준 1260번] DFS와 BFS (Python 파이썬) 풀이 방법

백준 1260번 <DFS와 BFS> 문제 보기

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

1260번: DFS와 BFS

 

 

백준 1260번 <DFS와 BFS> 문제 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
  start, end = map(int, input().split())
  graph[start].append(end)
  graph[end].append(start)

for i in graph:
  i.sort()

visited_b = [False for _ in range(n+1)]
visited_b[v] = True
  
def bfs(num):
  
  array = deque()
  array.append(num)

  while array:
    index = array.popleft()
    print(index, end = " ")
    for next in graph[index]:
      if visited_b[next] == False:
        visited_b[next] = True
        array.append(next)

visited_d = [False for _ in range(n+1)]
visited_d[v] = True

def dfs(num):
  array = deque()
  array.append(num)

  while array:
    index = array.popleft()
    print(index, end = " ")
    for next in graph[index]:
      if visited_d[next] == False:
        visited_d[next] = True
        dfs(next)

dfs(v)
print("")
bfs(v)

DFS 알고리즘에서는 재귀를 통해 깊이를 우선으로 노드를 탐색할 수 있도록 했다. BFS 알고리즘에서는 연결 정보가 담겨있는 graph를 돌며 array라는 deque를 이용하여 너비를 우선으로 노드를 탐색할 수 있도록 했다.

 

 

해당 문제는 DFS와 BFS 알고리즘을 공부한 후에 가장 먼저 풀어봐야 할 문제다.

수학의 정석 개념편 중 개념 예제 문제 같은 느낌

 

딱히 특별할 건 없고 제목 그대로 DFS와 BFS 기본을 다루는 문제다.