
[BOJ/Gold3] 1005번 ACM Craft - JAVA[자바]
·
PS/백준
난이도 : 골드 3유형 : 위상 정렬 / 동적 계획법링크 : https://www.acmicpc.net/problem/1005구현 시간 : 1시간 (못품) 문제풀이위상 정렬 알고리즘을 공부하고 나서 처음으로 풀어본 문제이다. 노드의 방문 순서를 구현하는건 쉬웠지만, 특정 건물마다 필요한 최대 시간을 구하는 방법을 생각해내지 못했다 ㅜ indegree[] 배열을 이용해 노드의 진입 차수를 저장하고, 방문마다 해당 노드의 진입 차수를 차감하여 위상 정렬을 구현했다. BFS에서 탐색 레벨마다 날짜를 계산했었던 토마토 문제가 기억이 나서 위상 정렬에도 반복마다 최대 시간을 누적하는 방식으로 최대 시간을 저장했다. 하지만 이 방법은 이전 단계에서 소요된 시간을 다음 단계에 반영하지 못하므로, 특정 노..