1260_bfs와dfs

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

1260번: DFS와 BFS

 

 

DFS와 BFS를 확인할 수 있는 좋은 문제이다. 나도 이 문제를 풀면서 오랜만에 다시 공부했던 것 같다.

 

이번에는 문제를 접하자마자 그냥 풀기보다는 알고리즘 공부를 하고 좀더 효율적으로 풀자 해서 이곳저곳에서 정보를 조금 찾아보고 공부를 했다.

 

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

n,m,start=map(int,input().split())
visited=[False]*(n+1)

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


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

for i in range(len(graph)):
    graph[i].sort()


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


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


dfs(start)
print()
visited = [False]*(n+1)
bfs(start)