poia0304   4년 전

제가 생각한 알고리즘은 다음과 같습니다.

좌표 i,j 위치에서 상,우,하,좌 의 방향을 각 0,1,2,3이라고 하고

D(i,j,d) = i,j에서 d방향으로 진행 후 M,N까지 갈 때 최소로 부수는 벽의 갯수

이렇게 알고리즘을 짰는데 질문에 올라온 

5 5
01000
01010
00010
11110
00000

이 테스트 케이스가 안돌아가서 문제가 무엇인지 계속 살펴보다가 도저히 잘 모르겠어서 질문드립니다.

알고리즘이 어디가 잘 못 된 것인지 알려주시면 감사하겠습니다.


jamrogramming   4년 전

dy(A, x, y, d)가 처음 호출돼서 계산될 때 그 값이 최적이라는게 보장이 안돼요.

비용이 0인 간선만 타고가서 x, y, d에 도달할 수 있는데 1인 간선을 먼저 발견하고 타버리는 경우가 생겨요.

sgchoi5   4년 전

두 가지를 조합해서 푸는게 제일 단순하고 일반적인 것 같습니다.

가중치가 없는 최단 경로 => BFS + 

block 은 최소한으로 => dp

visited 대신에 dp table 을 이용해서 벽을 최소한으로 이용하도록 ..... 

 

poia0304   4년 전

@jamrogramming

@sgchoi5

두 분 모두 답변 감사드립니다.

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