거리가 같은 먹이들에 대한 우선순위가 있는데, 처리 하신건가요??
16236번 - 아기 상어
저는 좀 무식하게 풀어서 시간이 오래걸렸네요.
일달 먹을 수 있는 고기들 찾아서 저장해 놓고, 각각의 거리를 구한다음 정렬을 했어요.(거리에 따른 우선순위는 정렬 기준으로 처리)
그리고 가장 먼저 먹어야 하는 고기의 거리의 누적시키고, 현재 상어의 위치를 갱신하는 방식.
그리고 반복. N 제한이 워낙 작아서 시도했던 방법이긴 한데...
4ms 나오신거 보니깐, 저보다 훨씬 효율적으로 짜신거 같아요. (사실 코드가 너무 길어서 제대로 보진 않았습니다..ㅜ)
"맞은 사람"에서 0ms 로 통과하신 분들의 코드를 분석해보는게 더 도움이 될거 같습니다. :)
댓글을 작성하려면 로그인해야 합니다.
lswoo3021 3년 전 1
안녕하세요 .. ! 또 이렇게 질문을 드리네요 ㅠㅡㅠ
이번 문제도 역시 .. TC는 맞는데 오답으로 나오네요 ..ㅠ
-최단거리를 찾을 때 visit[][]배열 외에 최단거리를 저장하는 distp[][]를 두어
현재 노드의 거리(dist[x + dx][y + dy]) = 이전 노드의 거리(dist[x][y]) + 1 로
모든 정점에 대해 최단거리 맵을 정리함.
-> 기출 문제중 bfs의 최단거리 문제는 처음보는 것 같네요... 일반적인 bfs에서
최단거리(또느 깊이, 레벨)을 파악하기 위해 약간의 변형이 필요한 문제.. 맞나요 ?
보통은 ㅠㅡㅠdfs든 bfs든 모든경우의수를 돌린뒤 min이나 max를 통해 단순비교하여 최소값/최댓값을
찾았는데요... 제가 너무 안일하게 생각했나봐요 ㅠ
정답률이 50%가 넘는데 다들 ㅠㅡㅠ 대단하신거같아요!
저는 bfs에서 거리를 기록하는 방법을 잘몰라서 헤맸는데 말이져 ㅠㅡㅠ
감사합니다!