문제
https://www.acmicpc.net/problem/1260
라인 1260: DFS 및 BFS
첫 번째 줄에는 정점의 개수 N(1≤N≤1,000), 모서리의 개수 M(1≤M≤10,000), 검색을 시작할 정점의 개수 V가 주어진다. 다음 M 라인에는 가장자리가 연결되는 두 정점의 번호가 지정됩니다. 임의의 두 정점 사이
www.acmicpc.net
DFS와 BFS로 그래프를 검색한 결과를 출력하는 프로그램을 작성하세요. 그러나 방문할 수 있는 정점이 여러 개인 경우에는 더 작은 정점 번호를 가진 정점을 먼저 방문하고 더 이상 방문할 수 있는 정점이 없으면 프로세스를 종료합니다. 정점 번호의 범위는 1에서 N까지입니다.
입력
첫 번째 줄에는 정점의 개수 N(1≤N≤1,000), 모서리의 개수 M(1≤M≤10,000), 검색을 시작할 정점의 개수 V가 주어진다. 다음 M 라인에는 가장자리가 연결되는 두 정점의 번호가 지정됩니다. 두 꼭짓점 사이에는 여러 가장자리가 있을 수 있습니다. 입력으로 주어진 에지는 양방향입니다.
인쇄
DFS 수행 결과는 첫 번째 행에 출력되고 BFS 수행 결과는 다음 행에 출력됩니다. V부터 방문한 지점이 순서대로 출력됩니다.
암호
import sys
from collections import deque
input = sys.stdin.readline
n,m,v=map(int, input().split())
graph=(() for _ in range(n+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()
dfsvisited=(False)*(n+1)
bfsvisited=(False)*(n+1)
def dfs(graph, u, dfsvisited):
dfsvisited(u)=True
print(u, end=' ')
for i in graph(u):
if not dfsvisited(i):
dfs(graph,i,dfsvisited)
def bfs(graph, u, bfsvisited):
queue=deque((u))
bfsvisited(u)=True
while queue:
v1=queue.popleft()
print(v1, end=' ')
for i in graph(v1):
if not bfsvisited(i):
queue.append(i)
bfsvisited(i)=True
dfs(graph,v,dfsvisited)
print()
bfs(graph, v, bfsvisited)문제 해결
기본적인 DFS 및 BFS 문제로 그 문제를 기반으로 다른 DFS/BFS 문제를 풀 수 있을 것 같습니다.