DFS와 BFS [백준 1260] - python

from collections import deque
import sys
input = sys.stdin.readline

def BOJ1260():
  def dfs(start, visited, graph):
    stack = []
    stack.append(start)
    print(start, end=" ")

    while stack:
      node = stack.pop()
      visited[node] = True

      for next in range(1, len(graph[node])):
        if visited[next] == False and graph[node][next] == 1:
          visited[next] = True
          dfs(next, visited, graph)

  def bfs(start, visited, graph):
    queue = deque()
    queue.append(start)

    while queue:
      node = queue.popleft()
      visited[node] = True
      print(node, end=" ")

      for next in range(1, len(graph[node])):
        if visited[next] == False and graph[node][next] == 1:
          visited[next] = True
          queue.append(next)

  N, M, V = map(int, input().split())
  graph = [[0 for _ in range(N+1)] for _ in range(N+1)]
  for _ in range(M):
    start, end = map(int, input().split())
    graph[start][end] = 1
    graph[end][start] = 1

  visited = [False for _ in range(N+1)]
  dfs(V, visited, graph)

  print()

  visited = [False for _ in range(N+1)]
  bfs(V, visited, graph)


BOJ1260()

 

접근방법 :

  0. dfs, bfs 가장 기본적인 문제이다.

  1. dfs는 재귀, bfs는 queue를 이용하였다. 

 

 

장애물 이였던 것 :

  1. dfs를 stack을 이용해서 풀어주었을때 출력해 주는 부분에서 계속 해결하지 못했다. 
재귀함수를 이용하는 것으로 변경하였고 방문해주는 순서대로 알맞게 출력해줄수 있었다.

  2. stack을 이용해서 푼 경우 1번에 2번과 4번 정점이 연결되어있는 경우 2번을 타고 들어가는 것이 아니라 2번 찍고 4번까지 가서 4번을 타고 들어가서 그러했다. 재귀로 변경하여 해결하였다. 
stack에 중간에 break를 넣어서 해결하려 했으나 점점 산으로 갔다.

 

 

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS