150365. 미로 탈출 명령어 / c++ / level3 / 45분
문제 및 코드
접근 방식
BFS
- 1차 시도 : 전형적인 BFS 대신 State 라는 구조체를 넣어서 거기에 현재 위치, 이동 거리, 경로 문자열을 담도록 해봤다. -> 시간 초과
- 2차 시도 : 1차에서 추가로 다음 이동할 위치와 목표 지점 간의 거리가 k보다 먼 경우를 제외하도록 했다. (다시 생각해보니 잘못된 식이었다. 거리가 K - Cost 보다 먼지를 확인해야함)
-> 시간 초과
- 백트래킹으로 바꿔서 시도해봤다. -> 시간 초과
- 문제를 다시 분석해보니 도달할 수 있는 경우 모든 경로 중 사전상 제일 앞의 경로를 반환하기 때문에, 진행경로 4가지를 사전상 빠른 순 (d, l, r, u) 으로 테스트해보고 그 중 하나라도 된다면 거기서 break 하도록 구현했다.
이렇게 했더니 문제가 하위 문제로 갈라지지 않고 반복문 한번 O(N)으로 끝날 수 있었다. -> 성공
생각해 볼 점
- 레벨 3쯤 오면 단순 구현으로는 해결할 수 없는 문제들이 주어진다. 문제를 잘 읽고 문제가 원하는 바를 제대로 파악하는 것이 중요하다.
(이 문제의 경우엔 진행 방향을 사전순으로 정렬한 뒤 성공하면 뒤에껀 계산할 필요가 없는 부분, 현재 위치에서 목표까지의 거리가 (K - Cost) 보다 크면 더 이상 진행할 필요가 없는 부분이 중요했던 것 같다.)
