[Algorithm] 백준 1260 : DFS와 BFS

문제
https://www.acmicpc.net/problem/1260
풀이 1
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/1260.%E2%80%85DFS%EC%99%80%E2%80%85BFS/DFS%EC%99%80%E2%80%85BFS.py
풀이 2
https://github.com/nowChae/algorithm/blob/master/boj/baekjoon1260.py

DFS와 BFS를 구현해보는 뼈대 문제였다. graph를 두 가지 방식으로 선언해서 풀어봤다.
풀이 1의 경우 graph 리스트는 정점이 연결된 상태를 담아둔 리스트이고
풀이 2의 경우 graph 리스트는 각 정점이 연결된 다른 정점의 번호를 담고 있다.

처음 이 문제를 풀었을 때 푼 풀이가 풀이 2에 해당하고, 이번에 DFS, BFS에 대해 다시 공부해보면서 푼 방식이 풀이 1이었다. 실행 시간은 풀이 1이 더 좋게 나온 것을 알 수 있었다. 아마도 풀이 2에서는 graph 리스트에 대해 한번 정렬을 해주기 때문에 그런 것이 아닌가 싶은 생각이 든다.

< 풀이 코드 1 >

from collections import deque
import sys

node, edge, start = map(int,sys.stdin.readline().split())

graph = [[False]*node for i in range(node)]

for i in range(edge):
  node1, node2 = map(int, sys.stdin.readline().split())
  graph[node1-1][node2-1] = True
  graph[node2-1][node1-1] = True

visited_d = [False]*node
visited_b = [False]*node


# 재귀를 이용해 구현
def dfs(start, visited, graph):
  visited[start-1] = True
  print(start, end=" ")

  for n in range(node):
    if (not visited[n]) and (graph[start-1][n]):
      dfs(n+1, visited, graph)

dfs(start, visited_d, graph)

# 큐를 이용해 구현
def bfs(start, visited, graph):
  queue = deque([start])
  visited[start-1] = True

  while queue:
    v = queue.popleft()
    print(v, end=" ")

    for n in range(node):
      if (not visited[n]) and (graph[v-1][n]):
        queue.append(n+1)
        visited[n] = True
    

print()
bfs(start, visited_b, graph)

< 풀이 코드 2 >

#DFS - stack, 재귀 함수를 이용해 구현 - 갈 수 있는 점까지 - 깊이 우선 탐색
#BFS - queue를 이용해 구현 - 현재 정점이 연결된 가까운 점부터 - 너비 우선 탐색

from collections import deque

point, line, start = map(int,input().split())

#해당 인덱스 정점에 연결된 정점 정리 리스트 
graph = [[] for x in range(point + 1) ]

for _ in range(line):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

#작은 정점 번호를 먼저 방문하기 위한 정렬
for g in graph:
  g.sort()

#DFS 정점 방문 상태 
visited_d = [False] * len(graph)

#DFS 함수 
def DFS(graph, v, visited):
  visited[v] = True
  print(v, end=' ')

  for i in graph[v]:
    if not visited[i]:
      DFS(graph, i, visited)

#BFS 정점 방문 상태
visited_b = [False] * len(graph)
def BFS(graph, start, visited):
  queue = deque(start)

  visited[start] = True
  while queue:
    v = queue.popleft()
    print(v, end=' ')

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


DFS(graph, start, visited_d)
print()
BFS(graph, start, visited_b)