[BOJ] 1260 - DFS와 BFS

사용 언어: Python3

문제

백준 1260

풀이

from collections import deque

# N: 노드(정점) 수, M: 엣지(간선) 수, V:시작 노드 번호
N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)] # 노드 번호가 1번부터 시작하기 때문 (0번은 그냥 버리기)

# 🌟 init graph (엣지는 양방향)
for _ in range(M):
  v1, v2 = map(int, input().split())
  graph[v1].append(v2)
  graph[v2].append(v1)

# 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
for i in range(N+1):
  graph[i].sort()

# 재귀 또는 스택
visited_dfs = [False] * (N+1)
def dfs(graph, start, visited):
  if visited[start] == False:
    # 방문한 노드 체크
    visited[start] = True
    print(start, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for node in graph[start]:
      dfs(graph, node, visited)

# 큐
visited_bfs = [False] * (N+1)
def bfs(graph, start, visited):
  q = deque([start])
  visited[start] = True

  while q:
    v = q.popleft() # 가장 왼쪽 원소 반환
    print(v, end=' ')

    for node in graph[v]:
      if not visited[node]:
        q.append(node)
        visited[node] = True

dfs(graph, V, visited_dfs)
print()
bfs(graph, V, visited_bfs)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기