728x90
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
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(len(graph)):
graph[i].sort() #번호 작은 순서대로 방문해야 함
visited = [False] * (N + 1)
def dfs(start):
print(start, end = ' ') #일단 첫 발자국을 찍고
visited[start] = True
for i in graph[start]: #그래프 첫 연결된 길부터 쭉 훑으며
if not visited[i]:
dfs(i) #계속해서 재귀 - 깊이우선 탐색이므로
visited[start] = True
def bfs(start):
q = deque([start])
visited[start] = True
while q:
v = q.popleft() #하나 꺼내고
print(v, end= ' ')
for i in graph[v]: #인접한것들 쫙 돌면서
if not visited[i]:
q.append(i) #큐에 추가함
visited[i] = True
dfs(V)
visited = [False] * (N + 1)
print()
bfs(V)오늘 DFS BFS 개념을 책을 통해 처음 배워봤는데..
넘넘 어렵당.
이 예제는 가장 기본적인 문제로, DFS와 BFS를 교재에 나와있는 그대로 쓰기만 하면 맞을 수 있는 문제였다.
각자가 어떤 방식으로 이루어지는지 그림을 통해 원리를 이해하는 것이 좋을 것 같다.
DFS는 그때그때 쭉 내려갔다 올라오면서 탐색해야하므로 재귀를 써야하고,
BFS는 너비우선 탐색이므로 deque를 이용해서 한번에 큐에 추가했다가 빼는 과정을 반복해야 한다.
이 때 visited에서 이미 참조가 끝났는지 아닌지 확인하면서 모든 노드를 훑는 순서를 거쳐야 하는 것 같다.
그리고 각자의 노드가 연결된걸 표시하기 위해서는 저렇게
graph[a].append(b)
graph[b].append(a) 와 같은 형식으로 써주는 것이 필요하다.
이는 반복이 생명인 것 같다. 여러 번 관련 예제를 풀어보며 익히자..
728x90