DHistory
[Baekjoon] DFS/BFS - 1260 DFS와 BFS 본문
문제
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
풀이
import sys
from collections import deque
from copy import deepcopy
n, m, v = map(int, sys.stdin.readline().rstrip().split())
graphs = [[] for _ in range(n + 1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().rstrip().split())
graphs[a].append(b)
graphs[b].append(a)
for i in range(1, n + 1):
graphs[i] = sorted(graphs[i])
visited = [False] * (n + 1)
def bfs(graphs, start, visited):
queue = deque([start])
visited[start] = True
while queue:
now = queue.popleft()
print(now, end=" ")
for v in graphs[now]:
if not visited[v]:
queue.append(v)
visited[v] = True
def dfs(graphs, start, visited):
visited[start] = True
print(start, end=" ")
for v in graphs[start]:
if not visited[v]:
dfs(graphs, v, visited)
dfs(graphs, v, deepcopy(visited))
print()
bfs(graphs, v, deepcopy(visited))
print()
채점 결과
'Computer Science > Algorithm' 카테고리의 다른 글
| [Baekjoon] DFS/BFS - 11724 연결 요소의 개수 (0) | 2023.09.04 |
|---|---|
| [Baekjoon] DFS/BFS - 1012 유기농 배추 (0) | 2023.09.04 |
| [Baekjoon] DFS/BFS - 2606 바이러스 (0) | 2023.09.04 |
| [Baekjoon] DFS/BFS - 16173 점프왕 쩰리 (Small) (0) | 2023.09.04 |
| [Baekjoon] Greedy - 17503 맥주 축제 (0) | 2023.08.30 |