티스토리 뷰

코딩/파이썬 백준

백준 1260 DFS와 BFS (파이썬)

박상어 2021. 12. 3. 19:50
728x90

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

 

1260번: DFS와 BFS

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

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import deque
 
def init(n):
    return [False for _ in range(n+1)]
 
def dfs(v):
    print(v, end=' ')
    check[v] = True
    for i in lst[v]:
        if not check[i]:
            dfs(i)
 
def bfs(v):
    dq = deque([v])
    while dq:
        v = dq.popleft()
        if not check[v]:
            print(v, end=' ')
            check[v] = True
            for i in lst[v]:
                if not check[i]:
                    dq.append(i)
 
N, M, V = map(int, input().split())
lst = [[] for i in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)
 
for i in lst:
    i.sort()
 
check = init(N)
dfs(V)
print()
check = init(N)
bfs(V)
 cs

 

'코딩 > 파이썬 백준' 카테고리의 다른 글

백준 1254 팰린드롬 만들기(파이썬)  (0) 2021.12.08
백준 14753 MultiMax (파이썬)  (0) 2021.12.06
파이썬 9536 여우는 어떻게 울지? (파이썬)  (0) 2021.12.01
백준 9322 철벽 보안 알고리즘 (파이썬)  (0) 2021.12.01
백준 15970 화살표 그리기 (파이썬)  (0) 2021.12.01
댓글