may900515   1달 전

좀 도와주십셔 ㅠㅠ

그냥  최단거리를 찾는건 이제 숙지가 되어서 알겠습니다만 벽을 부순다는 찬스를 쓰는거에서 어떻게 해야할지가 막막합니다..

헬프해주십시오 고수님들!!

sksdong1   1달 전

다익스트라 개념을 도입해서

벽을 만나면 가중치를 1로 두고 우선순위 큐에 담아요. 0의 가중치로 목적지에 도달 못하면 

1의 가중치로 선정된 위치 ( 벽의 위치)부터 도달이 가능한지 여부를 파악하면 될 것 같습니다.

뭐 물론 벽이 여러개면 가중치값이 2,3 늘어나구요

yclock   1달 전

먼저 BFS를 두 번 돌겁니다.

처음 BFS는 시작점에서 출발하고, 두 번째 BFS는 도착점에서 출발합니다.

이 행위를 통해 우리는 모든 칸에 대해서, "벽을 뚫지 않았을 때, '시작점과의 거리'와 '도착점과의 거리'"를 알 수 있습니다.


이제 모든 '벽'을 차례대로 보면서, 이 칸을 뚫고 지나갈 때의 최단거리를 다음과 같이 계산할 수 있습니다.

(거리) = min{ (이웃한 어떤 칸의 '시작점과의 거리') + (이웃한 어떤 칸의 '도착점과의 거리') }

yclock   1달 전

방금 제 소스를 보고 왔습니다.

BFS 한 번만 돌려서도 풀 수 있습니다.

Queue에 "현재 칸의 좌표"와 "여기까지 오면서 벽을 뚫었는 지의 여부", "거리" 정보를 같이 집어넣습니다.


이제, "벽을 뚫은 적이 있는지의 여부"에 따라서, 잘 돌리면 됩니다.....

may900515   1달 전


yclock

sksdong1

두분다 감사합니다.ㅜ

ㅜㅜ 원초적인 결함이.. 벽을 뚫는다는건 1이라는 자리를 0으로 바꿔줘야하는건가요? 아니면 1을 한번 지나갈수 있다고 설정을 해야할까요??

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