N : 정점
M : 간선
V : 정점 번호
연결된 정점을 주고, DFS와 BFS의 결과를 출력하는 문제이다.
반복문을 통해 변수 graph[a].append(b), graph[b].append(a)
를 해준다.
예제입력1을 넣어보면 [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]
이와 같이 출력되는데, 이는 인덱스 번호를 정점의 번호와 같다고 본다. 정점 1과 연결된 수가 2,3,4 정점 2와 연결된 수가 1,4 ... 라는 뜻이다.
graph[i].sort()
를 하는 이유는 문제에 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
라는 조건 때문이다.
그 후 dfs를 진행시켜!
dfs 코드는 굉장히 간단하당.
def dfs(v):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(i)
dfs
다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘
1. 현재 노드 방문 처리
2. 연결된 노드들 재귀적으로 방문 (방문안된 상태라면 재귀로 방문)
예제입력1을 예시로 해서 생각해보자. 시작 정점이 1
이므로 dfs(1)
이 진행된다.
visted[1] = True
로 방문체크를 해준 후 print(v)
로 정답을 출력한다.
그 후 graph[1]
(==[2,3,4])
를 반복문을 돌며 방문했으면 지나가고, 방문하지 않았으면 dfs(i)
를 재귀호출 해준다. 따라서 dfs(2)
가 진행된다.
또 반복문을 돌며 graph[2]
(==[1,4])
를 확인하는데, 1
은 맨 처음 방문했으므로 4
를 방문해준다. 그래서 dfs(4)
가 진행된다.
그 다음은 3
을 방문한다!
따라서 dfs 방문 정점 순서는 1 2 4 3
이 되는 것이다.
그다음은 bfs를 해보자.
dfs는 stack을 쓰는 반면 bfs는 queue를 쓴다. 따라서 from collections import deque
를 해주고 deque를 사용한다.
def bfs(v):
queue = deque([v])
visited[v] = True
while queue:
q = queue.popleft()
print(q, end=' ')
for i in graph[q]:
if not visited[i]:
queue.append(i)
visited[i] = True
bfs
그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복
예제입력1을 예시로 해서 생각해보자. 먼저 deque([1])
로 정점을 queue
에 집어넣는다. 그리고 visited[1]=True
로 방문 처리를 해준다. 그 후 while queue
로 큐가 빌 때까지 반복한다.
queue.popleft()
를 하여 큐에서 노드를 꺼낸 뒤 (현재 1) print(q)
로 결과를 출력해준다. 그럼 맨 처음 결과는 1
이 출력된다.
graph[1]
(==[2,3,4])
을 반복문을 돈다. 방문하지 않았으면, queue
에 해당 정점을 추가한다. 2,3,4 모두 방문하지 않은 상태이므로 queue
에는 deque([2,3,4])
가 들어가게 된다. 그리고 이 2,3,4는 visited[i]=True
로 모두 방문처리 된다.
그 다음 q=queue.popleft()
로 2
가 출력된다. graph[2]
(==[1,4])
는 이미 모두 방문처리 되었으므로 q = queue.popleft()
로 다시 돌아가 3
이 출력된다. 마찬가지로 다시 돌아가 4
가 출력된다.
따라서 bfs 방문 정점 순서는 1 2 3 4
가 되는 것이다.
끝!
from collections import deque
def dfs(v):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(i)
def bfs(v):
queue = deque([v])
visited[v] = True
while queue:
q = queue.popleft()
print(q, end=' ')
for i in graph[q]:
if not visited[i]:
queue.append(i)
visited[i] = True
N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)
for i 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()
dfs(V)
visited = [False] * (N+1)
print()
bfs(V)