nuricook   7달 전

안녕하세요,

이 문제는, BFS를 사용해서 풀었습니다.
벽이란 존재를 map에서 가중치를 1로 가지는 node로, 빈 방은 가중치를 0으로 가지는 node로 설정하고,
solve(int x, int y);은 "(x, y) ~ (N,M) 까지의 경로 중 가중치 합이 가장 적은 경로를 찾고, 해당 가중치 합을 반환하라"
라는 문제로 이해했습니다.

만약 빈 방으로만 N,M까지 가지 못하고 벽을 통과해야 했다면, 벽1개당 가중치 1씩 증가했을텐데요,
이 결과를 바로 출력하면 반대로 벽을 몇 개 뚫어야 목적지에 도착하는가? 에 대한 문제를 풀 수 있다고 생각했습니다.

실제로 결과도 잘 나오는 것 같네요. (추측입니다만..)

문제는, cache에 따른 "메모리 초과"로 나온다는게 문제랄까요 ^^;;;

아직, 문제 형태에 따른 적절한 cache를 사용하는게 익숙하지 않은 탓인지,
cache를 잡을 때, x, y (검색 중 현재위치) 와 x, y까지 오면서 생긴 가중치의 합으로 cache를 했습니다.


2 가지 걱정이 있습니다.

- 1. 과연 현재위치까지 오는데에 가중치의 합으로 cache를 구분하는게 옳은 방법인가?

- 2. 메모리 초과를 풀기위한 다른 접근방법은 무엇인가?

입니다.


혹시, 생각을 공유해주실 수 있다면 제게 도움이 많이 될 것 같습니당. :)

yukariko   7달 전

"벽이란 존재를 map에서 가중치를 1로 가지는 node로, 빈 방은 가중치를 0으로 가지는 node로 설정하고,solve(int x, int y);은 "(x, y) ~ (N,M) 까지의 경로 중 가중치 합이 가장 적은 경로를 찾고, 해당 가중치 합을 반환하라"라는 문제로 이해했습니다."


이것으로 보아 이 문제를 가중치가 있는 그래프문제로 생각할 수 있고, 시작점으로부터 끝점까지 가기위한 최단경로를 찾는 문제로 생각할 수 있습니다.

따라서 최단경로 알고리즘을 사용할 수 있죠.

oyj0594   7달 전

yukariko

어떻게 최단 경로 알고리즘으로 될까요??.. 벽을 많이 뚫어서 가는것이 최단 경로 일텐데, 경로의 길이는 길어져도 가중치의 합이 가장 낮은 것을 구하는 문제 아닌가요?

저는 이게 optimal 한 작은 문제가 큰 문제로 이어나가지 못한다고 봅니다. 따라서 DP는 힘들지 않을까요?? 제 생각입니다만,, 미래에 벽이 없는 루트가 등장하게 된다면 이전 데이터는 무의미이고, 그 루트를 따라야 되겠죠?


전 그래서 priority queue를 기반으로한 BFS 방법 밖에는 못 찾았습니다. 제가 잘못됬다면 알려주세요! ㅠㅎㅎ

yukariko   7달 전

말씀하신 풀이가 곧 다익스트라라고 할수있습니다.

이그래프에서 최단경로는 실제 길이가제일짧은것이 아니라 벽을 제일 조금뚫는것이 최단경로입니다.

nuricook   7달 전

yukariko

답변감사드립니다 :)

oyj0594

답변감사드립니다 :)

제가 공부한 책에 따르면 Priority queue를 기반으로 BFS를 통하는 것이 곧 다익스트라고 할 수 있다고 배웠습니다.

yukariko님의 말씀이 맞을 것 같네요 :)

혹시 Priority값을 어떻게 주셨나요?

저는 휴리스틱에서 쓰이는.. 멘하탄거리 + 벽값1을 가지고 해볼 예정입니다.. 잘되면 좋겠네요.

yukariko   7달 전

이 문제는 벽만 조금 뚫으면 되기때문에 멘하탄 거리는 우선순위에 반영되지 않습니다.

벽을 뚫었을때의 가중치만을 가지고 시작점 - 모든점 최단경로를 구하면 됩니다.

nuricook   7달 전

yukariko

감사합니다!

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