[BOJ] 백준 1260번 - DFS와 BFS (Python)

문제

문제 해결

DFS는 깊이 우선 탐색이므로 함수가 중첩되며 쌓이는 스택,재귀구조를 가지고, BFS는 너비 우선 탐색이므로 현재 노드의 인접 노드들을 모두 큐에 넣고 큐 순서대로 들어오면서 인근 노드들을 큐의 끝에 계속해서 넣어주는 방식으로 작동한다. 이론만 알고 백지 상태에서 DFS, BFS를 구현해보았다.

from collections import deque


def bfs_search(graph, v, visited):
  bfs_sequence = list()
  q = deque()
  q.append(v)

  while (q):
    visit_node = q.popleft()
    if visited[visit_node - 1] == False:
      bfs_sequence.append(visit_node)
      visited[visit_node - 1] = True
    for node in graph[visit_node - 1]:
      if visited[node - 1] == False:
        q.append(node)
        continue
  return bfs_sequence


def dfs_search(graph, v, visited):
  global dfs_sequence

  dfs_sequence.append(v)
  visited[v - 1] = True
  for neighbor in graph[v - 1]:
    if visited[neighbor - 1] == False:
      dfs_search(graph, neighbor, visited)
  return dfs_sequence


def _print(list):
  for i in range(len(list)):
    if i < len(list) - 1:
      print(list[i], end=' ')
    else:
      print(list[i])


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

for _ in range(m):
  s, e = map(int, input().split())
  graph[s - 1].append(e)
  if s not in graph[e - 1]:
    graph[e - 1].append(s)

for rel in graph:
  rel.sort()

print(graph)

visited = [False] * n
_print(dfs_search(graph, v, visited))
visited = [False] * n
_print(bfs_search(graph, v, visited))

실행 결과는 다음과 같다.

4 5 1
1 2
1 3
1 4
2 4
3 4
[[2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]
1 2 4 3
1 2 3 4

파이썬 1등 답안

# DFS와 BFS
import sys
input = sys.stdin.readline

def dfs(G, v, visited):
    global dfs_list

    visited[v] = True
    dfs_list.append(v)
    for w in sorted(G[v]):
        if not visited[w]:
            dfs(G, w, visited)


def bfs(G, v, visited):
    global bfs_list

    visited[v] = True
    queue = [v]
    while queue:
        n = queue.pop(0)
        bfs_list.append(n)
        for w in sorted(G[n]):
            if not visited[w]:
                visited[w] = True
                queue.append(w)


N, M, V = map(int, input().split())
G = [[] for _ in range(N + 1)]   # 0~N번 노드의 인접 노드
visited = [False] * (N + 1)             # N+1개를 만들어야 0~N번 노드의 값이 들어갈 수 있다.

for _ in range(M):                      # 너무 간단하게 이중리스트에 값을 채우는 모습 (...)
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

dfs_list = []
bfs_list = []

dfs(G, V, visited)
visited = [False] * (N + 1)
bfs(G, V, visited)

print(*dfs_list)
print(*bfs_list)

고찰

깨달은 점이 몇 가지 있다.

1. 1번부터 문제가 주어졌을 때의 해결 방향
2. 리스트 요소 한 번에 출력하기

나는 0이 시작이 아니고 1부터 노드가 시작되는 성가신 구조에서 살아남기 위해 v - 1, node - 1과 같은 코드를 작성하였는데, 역시나 예상한대로 멍청한 짓이었고, 해결법이 있을 줄 알았다.

총 N개인 0 ~ N-1까지의 범위를 N+1개인0 ~ N까지의 범위로 바꿔주고 그냥 평소대로 하면된다. 0은 없는 셈 친다.

또한 [1, 2, 3, 4]의 요소를 갖고있는 리스트를 1 2 3 4로 출력하기 위해 힘들진 않지만 ‘이게 맞나?’ 싶은 코드인 _print함수를 작성했는데 이 역시 존재할 이유가 없어졌다. 다음과 같이 활용하면 되는 것이었다.

리스트 요소 한 번에 출력하기 : print(*arr)

arr = [1, 2, 3, 4]
print(*arr)
# 1 2 3 4