[백 준/DFS-BFS] 1260: DFS와 BFS - 파이썬

2023.01.29 - [Algorithm] - [백 준/DFS-BFS] 1260: DFS와 BFS - 파이썬

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

1260번: DFS와 BFS

코드 풀이

from collections import deque
import sys
sys.setrecursionlimit(10**6) # 재귀로 풀기 위해
input = sys.stdin.readline

#도시의 개수, 간선정보, 시작노드 입력받기
n, m, start = map(int, input().split())

#모든 간선정보 입력받기, 현재 노드와 연결된 모든 노드를 담는 리스트
graph = [[] for _ in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  graph[a].sort()  #낮은 번호부터 방문하기 때문에 정렬하기
  graph[b].sort()  #낮은 번호부터 방문하기 때문에 정렬하기

visited_1 = [False] * (n+1) #dfs 방문정보
visited_2 = [False] * (n+1) #bfs 방문정보

def dfs(start):
  #현재 노드 방문처리
  visited_1[start] = True
  print(start, end = " ")
  #현재 노드와 연결된 모든 노드에 대하여
  for i in graph[start]:
    #아직 방문하지 않은 경우
    if not visited_1[i]:
      visited_1[i] = True
      dfs(i)
def bfs(start):
  q = deque()
  q.append(start)
  visited_2[start] = True
  while q:
    now = q.popleft()
    print(now, end = " ")
    for i in graph[now]:
      if not visited_2[i]:
        visited_2[i] = True
        q.append(i)


dfs(start)
print()
bfs(start)