6105 : 깊이 제한 DFS — IDDFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
무방향 그래프에서 시작 노드 S로부터 목표 노드 T까지 도달하기 위한 최소 탐색 깊이를 반복적 깊이 심화 탐색(IDDFS, Iterative Deepening DFS) 기법으로 찾으려 합니다.
IDDFS는 깊이 제한(Limit)을 0부터 시작하여 1씩 증가시키면서 깊이 제한 DFS를 여러 번 수행하는 방법입니다. 최대 탐색 깊이 D 이내에서 T에 최초 도달하는 최소 깊이를 구하시오. 도달 불가능하거나 최대 깊이를 초과하는 경우 -1을 출력합니다.
IDDFS는 깊이 제한(Limit)을 0부터 시작하여 1씩 증가시키면서 깊이 제한 DFS를 여러 번 수행하는 방법입니다. 최대 탐색 깊이 D 이내에서 T에 최초 도달하는 최소 깊이를 구하시오. 도달 불가능하거나 최대 깊이를 초과하는 경우 -1을 출력합니다.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)과 간선의 개수 M (0 ≤ M ≤ 1,000)이 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S, 목표 노드 T, 최대 깊이 제한 D (0 ≤ D ≤ 20)가 공백 구분되어 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S, 목표 노드 T, 최대 깊이 제한 D (0 ≤ D ≤ 20)가 공백 구분되어 주어집니다.
출력 설명
D 이하의 깊이 중 목표 노드 T에 최초 도달 가능한 최소 깊이를 출력합니다. 도달할 수 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2
2 3
3 4
4 5
1 4 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1도움
루프를 돌며
limit을 0부터 D까지 늘리고, 그 limit 하에서 깊이 제한 DFS(Depth-Limited DFS)를 매번 새롭게 호출하여 S에서 T를 찾을 수 있는지를 확인하십시오.