거울 설치문제는 BFS를 이용해서 다음 경로를 탐색하고 메모이제이션을 이용해서 최소한의 횟수로 이동할 수 있는 지점을 제한합니다.
이동방향은 거울을 설치하는 경우 두가지와 거울을 설치하지 않는 경우 한기지로 선택합니다.
예를 들어 오른쪽으로 이동하는 경우 거울을 설치하면 위, 아래로 이동하고,
거울을 설치 하지 않는경우 오른쪽으로 계속 이동하게 됩니다.
모든 경우를 계산하여 도착지점 문의 메모이제이션의 값이 최소 이동 횟수가 됩니다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준][슬라이딩윈도우] 11003 최솟값 찾기 (0) | 2019.02.03 |
|---|---|
| [백준][DP] 9184 신나는 함수 실행 (0) | 2019.02.02 |
| [백준][삼성SW검정] 14502 연구소 (0) | 2019.01.11 |
| [백준] 4673 셀프 넘버 (0) | 2019.01.09 |
| [백준][BFS] 1600 말이되고픈 원숭이 (0) | 2019.01.09 |