일단 본문에서 말하신 그 과정은 재방문이 아니라 경로 재설정에 더 가깝습니다.
그냥 큐로는 가장 가까운 길부터 탐색하기 때문인데요
만약 도착점으로 갈 수 있는 길이 (빈 공간 10칸과 문을 10개를 따고 가는 길)과 (빈 공간만 100칸 있는 길) 단 두 가지만 있다고 가정하면
일반 큐로는 문 10개를 따고 가는 길을 먼저 확인하고 값을 집어 넣기 때문에
(result[idx][nr][nc] == -1 || result[idx][nr][nc] > result[idx][qd.row][qd.col]+1) 가 아닌 (result[idx][nr][nc] == -1) 로 적으면 나중에 빈 공간만 100칸 있는 길을 찾아내도, 이미 result의 값이 -1이 아니기 있기 때문에 무시가 됩니다.
우선 순위 큐를 이용하시면 값이 작은 것부터 큐에서 빼오기 때문에 문을 1개 딴 순간부터 문 10개를 따야하는 길은 우선순위가 밀려나고, 빈 공간만 100칸 있는 길을 먼저 확인하게 되어 제대로 된 값을 출력하게 됩니다.
blackbbean 5년 전
보통 이문제를 풀 때,
3가지의 경우의 수로 나눠서 푸는것 같습니다.
https://stack07142.tistory.com...
(저는 이문제를 감도 못잡아서 이분의 블로그를 보고 해결 방법을 참조하였습니다.)
(0,0)에서 시작한경우
도착짐1에서 시작한 경우
도착점 2에서 시작한경우.
그 후 bfs를 돌려서 각각의 케이스에 따른 문을 연 갯수를 합해서 최종 답을 구하는데
저는 당연히 한번 방문했을 경우, 다시 방문해야하지 않을거라고 생각했습니다.
그래서 아래와 같은 코드를 구현하였고 ac를 받지 못하였습니다.
개선된 코드의 경우 다시 방문할 경우(이전 visited보다 현재 visited가 더 작을때)
를 허용하는 코드인데 이경우는 ac를 받았습니다.
어떤 경우에 방문했던 지점을 다시 한번 두번 방문해야하는지가 궁금합니다...
세가지 경우를 합해서 최종 답을 구하기 때문에 중복 방문 여부를 고려하지 않아도 된다고 생각했거든요....