validation (1) 썸네일형 리스트형 [TIL] 24.03.27 알고리즘, 챌린지반 과제 1. 알고리즘 문제 해결 도로포장(백준 1162): 다익스트라 알고리즘에 DP가 섞인 문제. 사실 DP라고 의식하지 않아도 풀다 보면 DP를 이용해서 풀게 된다. 당연하게도 브루트포스로는 풀 수 없다. 도로 중에서 포장할 도로를 고르는 경우의 수만 해도 50,000C20까지 주어질 수 있고, 각 경우의 수마다 최소 비용도 계산해야 한다. 이 문제를 해결하기 위한 로직은 꽤나 심플하다. 다익스트라 알고리즘을 사용하되, 다음 경로를 탐색할 때 도로를 포장하는 경우와 포장하지 않는 경우를 둘 다 고려해서 우선순위 큐에 넣어주는 것이다. 뭐 특정 개수 이하로 벽을 뚫고 미로를 탈출하라든지, 길의 종류가 있고 각 종류별로 제한된 수만큼만 이용하라든지 하는 DFS, BFS와 맥락이 정확히 같다. 이제 저 방법을 적.. 이전 1 다음
