코딩 미스입니다. 설명하신 알고리즘을 그냥 봤더니, 틀린 게 없는 거 같아서 직접 반례 데이터 가지고 디버깅 했습니다.
예를 들어, 이런 맵이 있다고 생각해 봅시다.
아래 그림을 보면서 이해하세요.
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가 되고 있죠.
mypark109 4년 전 1
제가 원래 했던 방식은
처음에 queue 하나에 player 번호 오름차순으로 좌표 값(i,j,player 번호)을 넣어두고,
queue 가 빌 때까지 계속 pop 시키면서 가능한 범위로 확장시키고, 확장된 곳은 queue에 넣어주었습니다.
이렇게 처리하면 계속 player 차례대로 확장이 가능하다고 생각을 했습니다. 그런데 12%에서 계속 틀리더군요ㅠ
그래서 검색을 통해 해설을 보고 풀었는데, player마다 queue를 따로 만들었고
각 player에서 파생되는 것들은 각 player의 queue에 넣어서 처리해주었더라고요.
풀긴했지만 첫번째 방식이 왜 틀린지, 두 방식이 왜 다른지 모르겠어서 질문을 올립니다.. 뭐가 다른 걸까요ㅠㅠ