[백준/BOJ] 1260 - DFS와 BFS

1260 - DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

코드

from collections import deque

def dfs(visited, start):
    visited[start] = True
    print(start, end=' ')

    for i in graph[start]:
        if not visited[i]:
            dfs(visited, i)

def bfs(visited, start):
    q = deque()
    q.append(start)
    visited[start] = True

    while q:
        v = q.popleft()
        print(v, end=' ')

        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = True


N, M, V = map(int, input().split())
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 g in graph:
    g.sort()

visited = [False] * (N+1)
dfs(visited, V)
print()
visited = [False] * (N+1)
bfs(visited, V)

한마디

graph 리스트에 넣은 간선들을 정렬해주면 문제에서 요구한대로 정점 번호가 작은 것부터 방문할 수 있다.

1260번: DFS와 BFS