SWEA 1249
-
[SWEA] #1249 _ 보급로Problem Solving/SWEA 2019. 7. 17. 07:00
[보급로] https://www.swexpertacademy.com/ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 처음에는 dp로 풀 수 있을 것이라고 생각하였다. 그러나, 아래와 같이 돌아가야하는 경우에 내가 생각한 dp로 풀면 올바른 답을 얻을 수 없다. dp의 결과로는 7이 최소 시간으로 구해지나, 최소 시간은 6이다. 이와 같은 경우를 고려하기 위해 bfs를 사용하였다. 지도에서 bfs로 그냥 탐색하면 시간이 너무 오래 걸리기 때문에 불필요한 탐색은 줄여야한다. dp의 결과를 기준으로 두고, dp의 값 보다 작은 경우에만 bfs로 탐색하여 최소 시간을 구하는 방식으로 구현하였다. (다른 사람의 풀이를..