728x90
반응형
[BAEKJOON]백준 1005번 ACM Craft - BFS(너비 우선 탐색), DP(다이나믹 프로그래밍), Topological Sort(위상 정렬)
백준 1005번 ACM Craft 백준 1005번 ACM Craft 설명 진입 차수 배열을 만들어서 해당 건물 전에 미리 지어야 할 건물이 있으면 해당 건물을 인덱스로해서 배열의 값을 1씩 증가시킨다. 각 건물마다 지을 때까지 걸리는 시간을 넣기위한 배열 dp를 만든다. 맨 처음에 진입 차수가 0인 건물을 큐에 다 집어 넣고, 그러면서 동시에 해당 건물의 dp 값도 해당 건물을 짓는데 걸리는 시간으로 다 바꿔준다(진입 차수가 0이니깐 그냥 그 해당 건물을 바로 지을 수 있음). 큐를 왼쪽부터 하나씩 빼면서 그 건물 다음으로 지을 수 있는 건물을 확인하면서 진입 차수를 1씩 빼준다. (다음 지을 수 있는 건물의 dp 값)과 (바로 전건물의 dp + 다음 지을 수 있는 건물 건설시간) 이 둘을 비교해서 더 ..
백준
2021. 7. 18. 14:24
728x90
반응형