[백준] 1260번: DFS와 BFS | 파이썬

알고리즘 분류: DFS, BFS

 

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

1260번: DFS와 BFS

 

먼저 일반적인 DFS, BFS 코드를 짜고 문제에서 정점 번호가 작은 것부터 방문하라고 되어있길래

dfs부터 코드를 고쳤습니다.

list = graph[start]
list.sort()

근데 이 코드 하나 dfs에 넣었더니 bfs까지 같이 결과가 바뀌더군요,,,

파이썬을 시작한 지 얼마 안돼서 문법을 잘 몰랐었는데 리스트 부분을 조금 더 공부해야겠어요!

 

내 풀이😊

from collections import deque

# 깊이 우선 탐색 DFS
def dfs(graph, start, visited):
  visited[start] = True
  print(start, end=' ')
  # 정점 번호가 작은 것부터 방문
  list = graph[start]
  list.sort()
  for i in list:
    if visited[i] == False:
      dfs(graph, i, visited)

# 넓이 우선 탐색 BFS
def bfs(graph, start, visited):
  queue = deque()
  queue.append(start)
  visited[start] = True
  print(start, end=' ')
  # 큐가 빌 때까지
  while queue:
    x = queue.popleft()
    for i in graph[x]:
      if visited[i] == False:
        queue.append(i)
        visited[i] = True
        print(i, end=' ')

# 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V 입력
n, m, v = map(int, input().split())

# 간선이 연결하는 두 정점의 번호
graph = [[] for _ in range(n + 1)]
for i in range(m):
  x, y = map(int, input().split())
  # 간선은 양방향
  graph[x].append(y)
  graph[y].append(x)
  

visited = [False] * (n + 1)
# DFS 실행
dfs(graph, v, visited)

print()

visited = [False] * (n + 1)
# BFS 실행
bfs(graph, v, visited)

 

아래는 백준 문제풀이를 올리는 깃허브 주소입니다.

https://github.com/Yiseull/baekjoon

GitHub - Yiseull/baekjoon