2917번 - 늑대 사냥꾼
메모리초과, 시간초과 등 문제가 해결되지 않길래 여러 고민을 했는데요
그 고민의 흔적을 공유드립니다.
문제 풀이방법
1) 나무로부터 BFS를 돌면서 가장 가까운 나무로부터 각 격자가 얼마나 떨어져있는지 확인
2) 데이크스트라 알고리즘을 응용하여 최대힙을 활용하여 시작점부터 끝점까지 이동
기본적인 풀이방법은 위와 같습니다. 물론 다른 풀이가 있을진 모르겠으나, 제 풀이는 그렇습니다.
먼저 1번에서 각 나무로부터 BFS를 돌때, 방문처리가 제대로 되지 않으면 메모리가 터집니다. 중복되는 요소들이 많이 들어가면 시간도 오래걸리고 큐도 터지므로, 메모리를 절약할 방법을 고안해야 합니다.
저는 최소힙을 활용하여 가장 가까운 나무를 마킹했습니다.
2번에서는 일반적인 데이크스트라에서는 최소힙을 사용하여 최단거리를 확인합니다.
이 경우는 최대거리를 확인하는 문제이므로, 최대힙을 활용해야 합니다.
파이썬의 경우 마이너스를 곱해서 최대힙을 구하는게 좋아보입니다.
나무와의 거리 측정 및 데이크스트라 구현이 가장 핵심이라고 보면 될것같습니다.
댓글을 작성하려면 로그인해야 합니다.
k550706 2년 전
메모리초과, 시간초과 등 문제가 해결되지 않길래 여러 고민을 했는데요
그 고민의 흔적을 공유드립니다.
문제 풀이방법
1) 나무로부터 BFS를 돌면서 가장 가까운 나무로부터 각 격자가 얼마나 떨어져있는지 확인
2) 데이크스트라 알고리즘을 응용하여 최대힙을 활용하여 시작점부터 끝점까지 이동
기본적인 풀이방법은 위와 같습니다. 물론 다른 풀이가 있을진 모르겠으나, 제 풀이는 그렇습니다.
먼저 1번에서 각 나무로부터 BFS를 돌때, 방문처리가 제대로 되지 않으면 메모리가 터집니다. 중복되는 요소들이 많이 들어가면 시간도 오래걸리고 큐도 터지므로, 메모리를 절약할 방법을 고안해야 합니다.
저는 최소힙을 활용하여 가장 가까운 나무를 마킹했습니다.
2번에서는 일반적인 데이크스트라에서는 최소힙을 사용하여 최단거리를 확인합니다.
이 경우는 최대거리를 확인하는 문제이므로, 최대힙을 활용해야 합니다.
파이썬의 경우 마이너스를 곱해서 최대힙을 구하는게 좋아보입니다.
나무와의 거리 측정 및 데이크스트라 구현이 가장 핵심이라고 보면 될것같습니다.