코딩 테스트/코딩테스트 - 학습
dfs bfs
안스 인민군
2023. 1. 14. 14:15
문제로 보는 정리
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
1. BFS & DFS 설계 (인접 리스트)
from collections import deque
n, m, v = map(int, input().split(" "))
visit = [False] * (n + 1)
arr = [[] for i in range(n + 1)]
for i in range(m):
a, b = map(int, input().split(" "))
arr[a].append(b)
arr[b].append(a)
def dfs(start):
print(start, end=" ")
visit[start] = True
for a in arr[start]:
if not visit[a]:
dfs(a)
def bfs(start):
queue = deque([start])
visit[start] = True
while queue:
q = queue.popleft()
print(q, end=" ")
for a in arr[q]:
if not visit[a]:
queue.append(a)
visit[a] = True
for i in range(1, n + 1): arr[i].sort()
dfs(v)
visit = [False] * (n + 1)
print()
bfs(v)2. BFS & DFS 설계 (배열)
from collections import deque
n, m, v = map(int, input().split(" "))
arr = [[0] * (n + 1) for i in range(n + 1)]
visit = [False] * (n + 1)
for i in range(m):
x, y = map(int, input().split())
arr[x][y] = 1
arr[y][x] = 1
def dfs(start):
print(start, end=" ")
visit[start] = True
for i in range(1, n + 1):
if not visit[i] and arr[start][i] == 1:
dfs(i)
def bfs(start):
queue = deque([start])
visit[start] = True
while queue:
q = queue.popleft()
print(q, end=" ")
for i in range(1, n + 1):
if not visit[i] and arr[q][i] == 1:
queue.append(i)
visit[i] = True
dfs(v)
print()
visit = [False] * (n + 1)
bfs(v)