blackbbean   5년 전

보통 이문제를 풀 때, 

3가지의 경우의 수로 나눠서 푸는것 같습니다.


https://stack07142.tistory.com...

(저는 이문제를 감도 못잡아서 이분의 블로그를 보고 해결 방법을 참조하였습니다.)

 

(0,0)에서 시작한경우

도착짐1에서 시작한 경우

도착점 2에서 시작한경우.

그 후  bfs를 돌려서 각각의 케이스에 따른 문을 연 갯수를 합해서 최종 답을 구하는데 

저는 당연히 한번 방문했을 경우, 다시 방문해야하지 않을거라고 생각했습니다. 

그래서 아래와 같은 코드를 구현하였고 ac를 받지 못하였습니다.


개선된 코드의 경우 다시 방문할 경우(이전 visited보다 현재 visited가 더 작을때)

를 허용하는 코드인데 이경우는 ac를 받았습니다.

어떤 경우에 방문했던 지점을 다시 한번 두번 방문해야하는지가 궁금합니다... 

세가지 경우를 합해서 최종 답을 구하기 때문에 중복 방문 여부를 고려하지 않아도 된다고 생각했거든요.... 

hello70825   5년 전

일단 본문에서 말하신 그 과정은 재방문이 아니라 경로 재설정에 더 가깝습니다.

그냥 큐로는 가장 가까운 길부터 탐색하기 때문인데요

만약 도착점으로 갈 수 있는 길이 (빈 공간 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칸 있는 길을 먼저 확인하게 되어 제대로 된 값을 출력하게 됩니다.

hello70825   5년 전

아 제가 설명을 잘못 해드렸는데 아래 사진과 같이 첫 번째 길이 도착점에 도착하고, 두 번째 길도 탐색을 하게 됩니다.(두 번째 길은 아직 가고 있는 중이므로)
그래서 두 번째 길은 도착점에 도착 하지도 못하고 탐색이 끝나게 됩니다.

아래 사진처럼 이해하시면 됩니다.

빨간길에 첫 번째 길, 파란길이 두 번째 길입니다

f45450a6-cef0-4807-bbd6-cc9bb492d6be

djm03178   5년 전

여담이지만 저 블로그 글에 있는 BFS는 사실 BFS라고 부르기 어렵고, 저런 식으로 거리가 갱신되는 지점을 재탐색하는 코드는 대체로 O((RC)^2)의 복잡도를 가지게 되지만, 그래프의 특성상 최악의 케이스를 만들기가 매우 어렵네요. 하나의 테스트케이스에 약 100만 칸을 탐색하도록 하는 케이스를 만들어내기는 했지만 이런 케이스를 100개씩 넣는 것이 문제의 의도가 아닐 수도 있을 것 같고, 하더라도 시간 초과가 나지는 않을 듯하여 그냥 두려고 합니다. 문을 여는 개수가 최소화되도록 탐색을 하려면 0-1 BFS 또는 다익스트라를 사용해야 합니다.

blackbbean   5년 전

이해하였습니다 :)

감사합니다 !! 

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