zyechun   2년 전

이상하게 c++로 짜면 메모리초과가 자주 뜨네요

왜 그런지 알려주실 수 있나요??

plzrun   2년 전

able하나로 다 처리하려고 하신거 같은데, 그것때문에 문제가 생깁니다.

BFS는 어떤 정점을 큐에 넣기전에 반드시 방문했음을 미리! 체크해줘야 해요.


예를 들어볼게요.


(5,5)를 기준으로 양 옆의 좌표인 (6,5)랑 (5,6)을 생각해볼게요. 지금 질문자님 기준대로 5,5의 able을 0으로 만든다음 6,5와 5,6을 큐에 푸시합니다. 6,5에 가서는 이제 인접 정점인 6,6이 큐에 들어가겠죠? 그러면서 6,5는 able이 꺼질겁니다. 그런데 6,6은 아직 able이 꺼지지 않았습니다. 그 상태에서 큐에 들어있는 5,6이 나와서 6,6을 또 큐에 넣게 됩니다. 6,6이 큐에 2번들어갔죠??

그럼 6,6을 기준으로 하면 7,7이 4번 들어가겠네요? 100,100은 2^100이나 들어가게 됩니다.


당연히 큐가 터져버려요.. ㄷㄷ

그러니까 맵의 정보와 visited는 항상 별개로 들고다녀야 하고, bfs는 큐에 넣기전에 반드시 그 값을 방문했음을 체크해줘야 합니다.



dfs는 들어가서 체크하고 bfs는 들어가기전에 체크하고! 이것만 명심해주시면 됩니다.

다만, 제 코드를 보시고 코딩 스타일을 바꾸셔야할 것 같습니다.

zyechun   2년 전

자세하게 답변해주셔서 정말 고맙습니다!

한 가지 의문점이 있는데요.

예를들어 (6, 6) 까지 최단경로를 구할 때

(6, 6)까지 가는 경로가 여러개 있잖아요.

위의 코드대로 실행하면, 처음에 (6,6)까지 가는 경로가 최단경로라는 말인데.

중간에 갈라져서 (6, 6)까지 가는 경로가 여러가지가 있지 않나요?

그러면 처음에 도착한 경우 말고, 큐에 남아있는 경로 중 나중에 (6, 6)까지 가는 경로가 최단경로인 경우가 있을 수도 있지 않나요?

plzrun   2년 전

그래서 깊이를 우선순위로 그래프 탐색(BFS)을 합니다.


원래 bfs가 최단경로를 구하는 알고리즘은 아니지만,

모든 간선의 가중치가 일정하다면, 최단경로를 구할 수 있습니다.

왜냐면, start->a->b->end 형식으로 start라는 정점에서 출발해서 a,b를 거쳐서 end정점에 도달했다고 할게요. 그럼 깊이 우선탐색을 했기때문에 해당 깊이의 길이(3)보다 end정점에 더 짧게 도달할 방법이 없습니다. 깊이 우선탐색을 했기 때문에 end가 queue에서 꺼내진 시점이 start로부터 가장 짧은 깊이였다는 것이죠. 그런데 모든 간선의 가중치가 같기 때문에 깊이(depth)자체가 start에서 end까지 가는 최단경로의 길이가 되버린 겁니다.


그러니까 6,6까지 가는 길은 여러경로가 있겠지만, 큐에서 6,6을 꺼낸시점이 출발점에서 6,6까지 가는 가장 짧은 depth길이가 되는거져~


그럼 이제 (6,6)이라는 정점을 현재 보고(큐에서 막 꺼내고), 거기가 최단경로라고 탕탕~ 못박아두는 겁니다.

그리고 그 정점에 인접한 애들을 큐에 넣겠죠?

그러다가 여기저기를 돌다 인접한 애들중에 6,6이 있으면 어떻게 될까요?

(6,6)은 이미 체크가 되어있기 때문에 그 정점을 큐에 넣을필요가 없습니다.

즉, 체크가 되어있다는 것은(visited가 체크되어있다는 것은) 해당 정점까지의 깊이가 이미 쾅쾅~ 낙인찍혔다는거죠.


아무튼 그래서 bfs는 깊이우선탐색을 하기 때문에, 현재 발견한 정점까지의 깊이(depth)보다 더 짧은 깊이로 도달하는 방법은 없게 됩니다.

그리고 그 모든 간선의 가중치가 같다면 결국 깊이 하나하나의 길이가 같다는 뜻이 되니까 최단경로의 길이를 구할 수 있다는 뜻이 됩니다.

zyechun   2년 전

아 제가 깊이 우선 탐색에 대해 잘못 이해하고 있었네요 !

정말 고맙습니다. 

이 사이트에 친절하신 분들이 되게 많은거 같아요 !

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