유형별 문제풀이 tony - 그래프 탐색, bfs, dfs

백준 1260번 DFS와 BFS 실버2

• 문제
• 코드
• 지난 번에 풀었던 풀이를 보니 graph 그려줄 때 sort를 해주면 searh 할 것 더해줄 때 하나하나 sort 안해줘도 된다.
• 이번에 푼 풀이 (저번 것이 더 나음)

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

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    x, y = map(int, input().rstrip().split())
    graph[x].append(y)
    graph[y].append(x)



def dfs():
    stack = []
    visited = [0] *  (N+1)
    stack.append(V)
    dfs_r = []

    while stack:
        now = stack.pop()
        if not visited[now]:
            dfs_r.append(now)
            visited[now] = 1
            to_visit = []
            for p in graph[now]:
                if not visited[p]:
                    to_visit.append(p)
            to_visit.sort(reverse=True)
            stack.extend(to_visit)
    print(*dfs_r)


def bfs():
    queue = deque()
    queue.append(V)
    visited = [0] *  (N+1)
    visited[V] = 1
    bfs_r= []

    while queue:
        now = queue.popleft()
        bfs_r.append(now)
        to_visit = []
        for p in graph[now]:
            if not visited[p]:
                visited[p] = True
                to_visit.append(p)
        to_visit.sort()
        queue.extend(to_visit)
    print(*bfs_r)

dfs()
bfs()