pda_pro12   6년 전

visit배열을 출력해보니 지나간 자리는 멀리 경유해서 탐색해 가는경우 이미 지나간 visit자리를 지나갈수가 없네요....

어떻게 해야 지나갈수 있을지.... 고수님들 도와주세요 ㅠㅠㅠ

djm03178   6년 전

벽을 부수지 않은 상태와 하나 부순 상태에 대한 방문 체크를 따로 해보세요.

pda_pro12   6년 전

제가 작성한 코드에서는 큐에 저장할때 벽을 한번 부수었는지 안부수었는지에 대한 정보를 저장해가면서 탐색하도록 작성하였습니다만. 

구조체 내에 boolean 형식의 변수를 선언해서 1을 만난다면 false로 바꾸고 벽을 부술수있는경우는 boolean변수가 true일 경우로 설계하였습니다. 

그런데 큐내에 저장되있던 좌표정보들이 한번 방문했던 부분을 다른 경로로 경유해서 올경우 경로가 겹처버리면 visit처리가 되있어서 큐에 더이상 삽입이 안되는거 같습니다. ㅠㅠㅠ 


벽을 부수지 않은 상태와 부순 상태에 대해서 방문체크를 따로 하려면 어떤 식으로 설계하는것을 말씀하시는건지 ㅠㅠㅠ 제가 잘 이해가 안됩니다! ㅠㅠ

djm03178   6년 전

쉽게 말해서 visit을 [1001][1001][2]와 같이 해서 [x][y][0]에는 "벽을 부수지 않은 상태에서 (x, y) 좌표에 대한 방문 여부", [x][y][1]에는 "벽을 부순 상태에서 (x, y) 좌표에 대한 방문 여부"를 저장할 수 있죠. 이렇게 하면 최단 거리를 구하는 문제에서 "어느 벽을 부수고 왔는가?"의 여부에 관계 없이 중복 방문을 제거하고 답을 구할 수 있습니다.

pda_pro12   6년 전

정말 감사드립니다 해결했습니다!

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