|
import sys
input = sys.stdin.readline
Vn, En, v = map(int, input().split())
V = {}
for i in range(1, Vn + 1) :
V[i] = []
for i in range(En) :
v1, v2 = map(int, input().split())
V[v1].append(v2)
V[v2].append(v1)
for i in range(1, Vn + 1) :
V[i].sort()
gone = []
def DFS(now) :
print(now, end = ' ')
gone.append(now)
for i in V[now] :
if not i in gone :
DFS(i)
DFS(v)
print()
gone = []
def BFS(now) :
que = [now]
while que :
q = que[0]
print(q, end = ' ')
gone.append(q)
del que[0]
for i in V[q] :
if not i in gone and not i in que :
que.append(i)
BFS(v)
|
인풋받은 선들을 이용해 각각의 점이 어느 점과 연결되어있는지 딕셔너리를 작성해준다.
(선이 양뱡향으로 이루어져 있으므로 v1>v2, v1<v2를 모두 추가해준다.)
여기까지 하고 나면 구현은 복붙이다. DFS는 Nqueen에서 썼던 dfs이고, BFS는 외판원 순회에서 썼던 BFS이다.
이때 각각의 재귀함수가 독립된 결과를 내는 것이 아니라 다 합쳐 하나의 결과(=전체 탐색)을 만드는 것이 목적이므로 gone을 함수의 입력변수가 아니라 글로벌 변수로 설정한 것만이 다르다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2606 바이러스 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 11724 연결 요소의 개수 (0) | 2021.11.20 |
| 파이썬 백준 1197 최소 스패닝 트리 (0) | 2021.11.19 |
| 파이썬 백준 5639 이진 검색 트리 (0) | 2021.11.19 |
| 파이썬 백준 1991 트리 순회 (0) | 2021.11.19 |