mypark109   4년 전

제가 원래 했던 방식은

처음에 queue 하나에 player 번호 오름차순으로 좌표 값(i,j,player 번호)을 넣어두고,

queue 가 빌 때까지 계속 pop 시키면서 가능한 범위로 확장시키고, 확장된 곳은 queue에 넣어주었습니다. 

이렇게 처리하면 계속 player 차례대로 확장이 가능하다고 생각을 했습니다. 그런데 12%에서 계속 틀리더군요ㅠ


그래서 검색을 통해 해설을 보고 풀었는데, player마다 queue를 따로 만들었고

각 player에서 파생되는 것들은 각 player의 queue에 넣어서 처리해주었더라고요.


풀긴했지만 첫번째 방식이 왜 틀린지, 두 방식이 왜 다른지 모르겠어서 질문을 올립니다.. 뭐가 다른 걸까요ㅠㅠ
 

chogahui05   4년 전

코딩 미스입니다. 설명하신 알고리즘을 그냥 봤더니, 틀린 게 없는 거 같아서 직접 반례 데이터 가지고 디버깅 했습니다.

예를 들어, 이런 맵이 있다고 생각해 봅시다.

아래 그림을 보면서 이해하세요.

s[4]가 2라고 해 봅시다. 그리고 (1,4) (1,5) (2,5) 순으로 Expand가 된다고 생각합시다.

그러면 (1,4)가 Expand 되면서 탐색한 것은 a, (1,5)가 Expand 되면서 탐색한 것은 b가 됩니다. 그런가요?

그런데, (2,5)를 Expand 시킨다고 생각해 보자고요. 그러면 어떻게 될까요?

제가 ?로 칠한 곳은 원래 (2,5)를 Expand 시킬 때 같이 Expand가 되어야 해요. 그런데, 안 되고 있어요. c로만 Expand가 되고 있죠.

chogahui05   4년 전

이것은 (1,4) (1,5) (2,5)를 별개로 보고 BFS를 돌리기 때문인데요.

사실 BFS의 특성을 잘 생각해 보면 저 셋을 어떤 순서로 돌리느냐에 따라서 새로 확장되는 노드는 독립이 아니라 종속임을 알 수 있어요.

왜냐하면 BFS의 특성상, 이미 간 곳은 다시 가지 않는데

AA라는 것을 Expand 하고 BB라는 것을 Expand 하면 CC라는 친구를 Expand 할 때

갈 수 있음에도 가려져서 못 가는 극단적인 경우가 생길 수 있어요. 제가 보여드린 예가 그러한 예에요. 그것 때문에 답이 잘못 나오는 경우가 있고요.

12%에서 틀린 예는 그러한 것 때문에 틀린 거에요.

이를 해결하기 위해서는, 내가 탐색을 다 끝냈을 때 위치를 임시 Queue이던 Vector에 저장해 놓고

다음에 다시 탐색하기 시작했을 때 먼저 한꺼번에 Queue에 넣고 시작하는 방법이 있어요. 코딩 미스이고요.

이 인풋에 대해서 답이 얼마가 나와야 할지 잘 생각해 보세요.

mypark109   4년 전


아하 동시에 확장을 해야하는데 한개씩 확장을 하다보니 가려지게 돼서 미스가 발생했네요..! 한 시간동안 설명해주신 것 곰곰이 생각해보다가 이제 이해했습니다. 

직접 디버깅도 해주시고 ㅠㅠ 정말.... 상세한 설명 감사합니다!! bb

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