Python 코딩테스트

DFS/BFS: 백준 1260 파이썬

bgeun2 2021. 8. 18. 16:27
반응형

문제:

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

풀이:

from collections import deque

n, m, v = map(int, input().split())

array = [[] for _ in range(n+1)]
result_dfs = 0
result_bfs = 0
visited_dfs = [False] * (n + 1)
visited_bfs = [False] * (n + 1)

for i in range(m):
    x, y = map(int, input().split())
    array[x].append(y)
    array[y].append(x)

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


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


def bfs(array, start, visited_bfs):
    queue = deque([start])
    visited_bfs[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in array[v]:
            if not visited_bfs[i]:
                queue.append(i)
                visited_bfs[i] = True


dfs(array, v, visited_dfs)
print()
bfs(array, v, visited_bfs)
반응형