알고리즘 - Python / 백준 - 1260번 : DFS와 BFS

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

 

---

풀이

• 양방향 DFS와 BFS를 구현하기만 하면 되는 문제이다
• DFS는 스택으로 , BFS는 큐로 구현하면 된다.
• 노드는 딕셔너리 안에 리스트 형태로 저장하고 , 양방향 이기 떄문에 2번 저장해준다.

 

import sys

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

dic = {}

def dfs(dic, root):
  visited = []
  stack = [root]

  while stack:
    n = stack.pop()
    if n not in visited:
      visited.append(n)
      if n in dic:
        sub_stack = list(set(dic[n]) - set(visited))
        sub_stack.sort(reverse=True)
        stack += sub_stack
  
  for i in range(0,len(visited)-1):
    print(visited[i], end=" ")
  print(visited[len(visited)-1])

def bfs(dic, root):
  visited = []
  stack = [root]

  while stack:
    n = stack.pop(0)
    if n not in visited:
      visited.append(n)
      if n in dic:
        sub_stack = list(set(dic[n]) - set(visited))
        sub_stack.sort()
        for i in range(0,len(sub_stack)):
          stack.append(sub_stack[i])

  for i in range(0,len(visited)-1):
    print(visited[i], end=" ")
  print(visited[len(visited)-1])

for _ in range(m):
  nd1, nd2 = map(int , sys.stdin.readline().split())
  if nd1 not in dic:
    dic[nd1] = [nd2]
  else:
    dic[nd1].append(nd2)
  
  if nd2 not in dic:
    dic[nd2] = [nd1]
  else:
    dic[nd2].append(nd1)

dfs(dic, k)
bfs(dic ,k)

---