Notice
Recent Posts
Recent Comments
반응형
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 하버-보슈법
- 다익스트라
- 국민의 힘 뿌리
- 백준
- 비상계엄
- ccw
- 티스토리챌린지
- dfs 백트래킹
- 파비우스 전략
- Prim
- 구조론
- 분할정복
- 내란죄
- 왈왈왈
- LCA
- dfs
- 알고리즘
- 유니온 파인드
- 이분 탐색
- Python
- union find
- 내란수괴 윤석열
- BFS
- 재귀함수
- DP
- 프림
- 내란수괴
- 윤석열
- 오블완
- 투 포인터
Archives
- Today
- Total
Toolofv 님의 블로그
[Python] 백준 - 1260 DFS와 BFS 본문
반응형
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
문제해결방법 -
1. DFS, BFS 알고리듬의 방문순서를 출력한다.
import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**8)
n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
vd = [0 for _ in range(n+1)]
vb = [0 for _ in range(n+1)]
cnt_D = 1
cnt_B = 1
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, n+1):
graph[i].sort()
def dfs(x):
global cnt_D
vd[x] = cnt_D
print(x, end=' ')
for next in graph[x]:
if vd[next] == 0:
cnt_D += 1
dfs(next)
def bfs(x):
global cnt_B
q = deque()
q.append(x)
vb[x] = cnt_B
while q:
x = q.popleft()
print(x, end=' ')
for next in graph[x]:
if vb[next] == 0:
cnt_B += 1
vb[next] = cnt_B
q.append(next)
dfs(r)
print()
bfs(r)
반응형
'Algorithm' 카테고리의 다른 글
[Python] 백준 - 1012 유기농 배추 (0) | 2024.06.11 |
---|---|
[Python] 백준 - 2667 단지번호붙이기 (1) | 2024.06.11 |
[Python] 백준 - 3015 오아시스 재결합 (1) | 2024.06.07 |
[Python] 백준 11049 - 행렬 곱셈 순서 (0) | 2024.06.05 |
[Python] 백준 2293 - 동전 1 (1) | 2024.06.05 |