24479: 알고리즘 수업 – 깊이 우선 검색 1
첫 번째 줄은 꼭지점의 수 N(5 ≤ N ≤ 100,000), 모서리 수 M(1 ≤ M ≤ 200,000), 시작 꼭지점 R(1 ≤ R ≤ N)을 제공합니다. 에지 정보 uv는 다음 M 라인에 주어지며 정점 u와 정점 v의 가중치는 1입니다.
www.acmicpc.net
암호
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 정점
graph = (() for _ in range(n+1))
visited = (0) * (n+1) # 방문 순서 저장. 0이면 방문 X
c = 1
def dfs(graph, v, visited):
global c
visited(v) = c # 방문하면 순서 나타내기
for i in graph(v):
if visited(i) == 0: # 방문 안한 노드이면
c += 1
dfs(graph, i, visited) # dfs 재귀
# m개의 연결된 간선 정보 입력받기
for i in range(m):
a, b = (map(int, input().split()))
graph(a).append(b)
graph(b).append(a)
# print(graph)
for i in range(n+1): # 오름차순으로 인접노드 방문하기 위해 정렬
graph(i).sort()
# print(graph)
dfs(graph, r, visited)
for i in range(1, n+1):
print(visited(i))이 문제 해당 노드를 몇 번이나 방문했습니까?출력하는 문제입니다.
첫 번째, dfs 함수보고 방문 순서는 c다음을 사용하여 계산 방문한 순서기록되었습니다
Visited는 1부터 n까지 모든 노드를 0으로 초기화했습니다. 방문할 수 없는 노드라면 0으로 출력하라는 문제가 있어서 0으로 설정했습니다.
다음으로 그래프의 노드 1에서 dfs를 사용하여 인접 노드를 방문합니다. 해당 노드를 방문했다면 방문 순서 기록해, 방문하지 않은 노드인 경우 c+1을 수행하고 dfs를 반복합니다.하다.
국선 정보 입력받은 부분은 다음과 같습니다.
문제에서 Edge 정보는 M줄에 u와 v의 형태로 수신된다고 하여 for문을 m번 반복하여 입력을 받는다.
u, v는 서로 연결된 노드의 정보이렇게 말한다 1 4이렇게 입력하면 1번과 4번이 연결되어 있다는 뜻이고, 그래프(1)에 4를 추가하고 그래프(4)에 1을 추가합니다.이렇게 해야 각 노드에 연결된 모든 노드를 알 수 있습니다.
예제 입력에서와 같이 5개의 Edge 정보를 받아 각각의 노드에 따라 그래프에 추가하면 오른쪽 그림과 같은 그래프가 됩니다.
목록의 특성상 숫자 0부터 시작합니다. 인덱스 1에서 인덱스 n까지 노드 1~n에 대한 정보 저장이를 위해 초기에 n+1개의 그래프가 생성되었습니다. (인덱스 0은 무시됩니다.)
예제 입력에서는 노드 5에 대한 정보가 제공되지 않으므로 그래프(5)에 정보가 없습니다.
모든 노드에 대한 인접 노드 정보가 입력되면 문제에서 인접한 노드는 오름차순으로 방문한다고 하셨으니 각 노드의 인접 노드 목록은 오름차순 정렬 그렇습니다
준비과정이 끝나면 dfs 실행하다.
마지막으로 결과 출력 부분은 다음과 같습니다.
Visited 역시 그래프와 같이 index 0은 무시하지만 index 1부터 n까지 해당 노드의 방문 순서를 저장한다.
따라서 for 문을 통해 Visited(1)에서 Visited(n)까지 값을 출력할 수 있어요.
Ikote DFS/BFS 강의를 듣고 관련 문제를 백준에서 풀었습니다.
처음이라 고생하는 시간이 오래 걸렸지만 조금씩 잘못된 부분을 수정하면서 해결할 수 있었습니다.