백트래킹은 모든 호출이 끝이 나야만 해답을 찾을 수 있기 때문에, 이러한 깊이우선 탐색은 이 문제에서 비효율적이다. 이 방법 대신 너비우선탐색 기법을 이용하여 버튼 누름 횟수를 기준으로 가장 먼저 목표 온도에 도달할 때까지 탐색하고 중단하는 방법으로 설계해 보자.
34도에 도달하게 되면 모든 연산을 중지하고 결과를 얻을 수 있다. 너비우선탐색으로 탐색하여 목표 온도에 도달하는 경우 계산량은 이 탐색 버튼의 수 3과 목표 온도에 도달하는 최적의 횟수 cnt에 비례하므로 계산량을 줄일 수 있다.
순서대로 하면 cnt가 적은 순서대로 차례로 계산이 된다. 목표 온도에 도달하면 가장 적은 cnt로 도달한 것임을 알 수 있다.
'Algorithm > Etc' 카테고리의 다른 글
| [DFS] 치즈 ( p. 161 ) (0) | 2020.10.07 |
|---|---|
| [DFS] flood fill ( p.78 ) (0) | 2020.10.07 |
| count inversion using merge sort (0) | 2020.09.27 |
| int형 최대, 최소 설정 (0) | 2020.09.27 |
| [DFS] n-Queen (0) | 2020.09.26 |
