[BOJ] 백준 1260 DFS와 BFS

태환·2024년 1월 29일
0

Coding Test

목록 보기
24/151

📌 [BOJ] 백준 1260 DFS와 BFS

📖 문제

📖 예제

📖 풀이

from collections import deque
import sys

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited_DFS = [0] * (N+1)
visited_BFS = [0] * (N+1)
for _ in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a] += [b]
  graph[b] += [a]



def DFS(V):
  visited_DFS[V] = 1
  print(V, end=' ')
  for i in sorted(graph[V]):
    if visited_DFS[i] == 0:
      DFS(i)

def BFS(V):
  queue = deque()
  queue.append(V)
  visited_BFS[V] = 1
  while queue:
    a = queue.popleft()
    print(a, end=' ')
    for i in sorted(graph[a]):
      if visited_BFS[i] == 0:
        visited_BFS[i] = 1
        queue.append(i)

DFS(V)
print()
BFS(V)

DFS/BFS 함수를 이용하여 각각의 순서를 출력한다.
처음 연결된 노드들을 입력할 때 각 노드의 연결된 노드들은 순서대로 추가되지 않는 것을 주의해야한다.
이를 위해 각 함수의 그래프 내 원소의 연결된 원소를 하나씩 가져오는 for문에서 sorted()함수를 이용하여 원소 내의 연결된 원소들을 오름차순으로 만들어주어야 한다.

profile
연세대학교 컴퓨터과학과 석사 과정

0개의 댓글