글 읽기 - 모든 좌표에대하여 가장 가까운 점을 찾는 알고리즘은 뭔가요??

문제유형이 대충

[1][0][0][0][0]

[0][0][0][0][1]

[0][0][0][1][0]

이러한 격자가 있으면, 어디다가 쓰레기통을 둬야 모든 1에서 공평하게 갈 수 있는가 를 물어보는 문제인데

이건 각 0점에대하여 BFS를 실시하는 걸 물어보는 전수조사인가요??

혹은 이분탐색..???

아니면 이런유형의 알고리즘이 있나요?

거리가 택시 기하학으로 주어지는 경우에는

이분탐색 + 절댓값의 특성을 이용해서 푸실 수 있습니다.

어떤 문제를 보시고.. 이런 글을 올리시게 된 것일까요?

댓글 감사합니다.

문제 좀 찾아봤는데 이게 제일 비슷했네요

근데 이건 격자말고 그래프로 주어진 경우고

저는 처음부터 격자인 상태의 문제를 봐서..ㅠㅠ

격자랑 그래프는 좀 다른 건데.. 흐음..

링크주신 문제를 보니.. 2개 지점에서 다익스트라를 돌리면 될 거 같은데요. 격자로 주어진 거라면..

이야기가 달라질 수도 있어요. 그래프를 모델링 하는 방법이 달라질 수 있거든요. 그리고 그걸 구축하는 법도 달라지고요.

조건에 따라서 알고리즘이 달라지는 경우가 상당히 많아요.

문제를 정확히 알아야 다른 분들이 답변을 해 드릴 듯 싶네요.

혹시 이런 류랑 비슷한 것들인가요?

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge