백준 1260번 : DFS와 BFS(Python, 파이썬)

풀어본 문제를 복습하고 있다.

 

'단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고'라는 조건을 주의해야 한다.

 

인접 리스트의 요소에 접근했을 때 BFS의 경우 인접 리스트 요소를 오름차 순, DFS의 경우 인접 리스트 요소를 내림차 순으로 정렬해주어야 한다.

 

예를 들면 인접 리스트의 특정 요소 adj[i] = [2,5,1]이 있다고 가정하자.

 

오름차 순으로 정렬 시 adj[i] = [1,2,5], 내림차 순으로 정렬 시 [5,2,1]이다.

 

원소들은 정점이므로 queue와 stack에 담아주면 queue = [... 1, 2, 5], stack = [... 5, 2, 1]로 쌓이게 된다.

 

이렇게 되면 탐색을 진행 시 queue와 stack 둘 다에서 정점 번호가 작은 것을 먼저 꺼낼 수 있게 된다. (queue는 선입선출, stack은 선입 후출이므로)

 

import sys, collections

def bfs(n, st, adj, res1):
  visited = [0] * (n+1)
  q = collections.deque()
  q.append(st)

  while q:
    v = q.popleft()
    if not visited[v]:
      visited[v] = 1
      res1.append(v)

    for sv in adj[v]:
      if not visited[sv]:
        q.append(sv)

  return res1


def dfs(n, st, adj, res2):
  visited = [0] * (n+1)
  stack = []
  stack.append(st)

  while stack:
    v = stack.pop()
    if visited[v] == 0:
      visited[v] = 1
      res2.append(v)

    for sv in sorted(adj[v], reverse=True):
      if not visited[sv]:
        stack.append(sv)
        
  return res2

n, m, v = map(int, sys.stdin.readline().split())

adj = [[] for _ in range(n+1)]

for _ in range(m):
  s, e = map(int, sys.stdin.readline().split())

  adj[s].append(e)
  adj[e].append(s)

for i in range(1, len(adj)):
  adj[i] = sorted(adj[i])

print(" ".join(map(str,dfs(n, v, adj, []))))
print(" ".join(map(str,bfs(n, v, adj, []))))