1260-DFS와 BFS

<문제>

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

1260번: DFS와 BFS

<풀이>

https://hae-sooo97.tistory.com/25

탐색(DFS/BFS)

※주의점 :  dfs함수를 호출한후 visited 배열을 원래대로 다시 돌려놔야한다!!

              위 링크에 설명대로  dfs(graph,n,visited)와 같이 인자를 3개를 집어넣으면 런타임 에러가 발생함!

              입력시 int(input()) 보다 import sys를 이용해 sys.stdin.readline().split()를 사용하면 시간단축 가능

<코드>

-파이썬-

from collections import deque
import sys

def dfs(n):
    visited[n] = True
    print(n,end = ' ')
    for i in graph[n]:
        if not  visited[i]:
            dfs(i)


def bfs(start):
    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

n,m,start = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,n+1):
    graph[i].sort()
visited = [False]*(n+1)
dfs(start)
visited = [False]*(n+1)
print()
bfs(start)