7307 : 재귀 트리 경로 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
루트 노드(1번)에서 임의의 노드까지의 경로 중, 경로 상의 노드 값(가중치)의 합이 정확히 $S$가 되는 경로를 모두 출력하십시오.
DFS(재귀)로 모든 경로를 탐색합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
DFS(재귀)로 모든 경로를 탐색합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 노드 수 $N$과 목표 합 $S$가 주어집니다. ($1 \le N \le 1{,}000$)
둘째 줄에 각 노드의 가중치 $N$개가 주어집니다.
이어서 간선 정보가
둘째 줄에 각 노드의 가중치 $N$개가 주어집니다.
이어서 간선 정보가
u v w 형식으로 주어집니다.출력 설명
루트에서 임의의 노드까지 경로 상 노드 값의 합이 $S$인 경로를 한 줄에 하나씩 출력합니다.
없으면
없으면
NONE을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10
1 2 3 4 5
1 2 1
1 3 1
2 4 1
2 5 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 3 4도움
DFS로 루트부터 재귀적으로 노드를 방문하며 경로를 유지합니다. 현재 경로의 노드 값 합이 $S$이면 출력합니다. 리프 노드까지 방문 후 백트래킹합니다.