백준 3860번 할로윈 묘지
< 백준 3860번 할로윈 묘지 - 마코 코딩박 >
사용한 알고리즘: 벨만 포드
WxH 크기의 묘지 그리드를 주고, 입구에서 출구로 가능한 빠르게 탈출하는 문제였습니다.
저는 밸만포드를 사용하여 문제를 해결하였습니다.
주의할점은, 문제에는 나와있지 않지만 원문에 따르면 Exit에 도착하면 다시 움직이지 않고 바로 탈출이라고 합니다.
문제풀이는 다음과 같습니다.
(1) (생각)
묘지의 그리드 수는 W*H 개 입니다. (0,0), (1,0) , ... , (W-1, H-1) 에 각각 0, 1, ..., W*H-1 의 index를 붙여주어 생각할 것입니다. (x,y) 의 index 는 y*W+x 입니다.
( 고등학교에서 흔히 썼듯이 x축을 column으로(가로) y축을 row으로(세로) 생각해주었습니다. )
(2) (코드 36~66)
index 붙인 각각의 칸 (i,j)에서 움직일 수 있는 <칸, 걸리는 시간>을 vector배열로 저장했습니다.
(3) (코드 67~80)
밸만포드 구현입니다. 'dist[k]: index=0 (=입구 칸 (0,0)) 에서 index=k 칸으로 이동하는데 걸리는 시간' 으로 설정했습니다. 초기 dist[0]=0이고 나머지는 Infimum입니다.
과정(2) 에서 만들어 놓은 각 칸 별로 <이동할 칸, 걸리는 시간>을 갖고 밸만포드 돌립니다. 이과정에서 minuscycle 이 있는지 찾아줍니다.
사용한 알고리즘: 벨만 포드
WxH 크기의 묘지 그리드를 주고, 입구에서 출구로 가능한 빠르게 탈출하는 문제였습니다.
저는 밸만포드를 사용하여 문제를 해결하였습니다.
주의할점은, 문제에는 나와있지 않지만 원문에 따르면 Exit에 도착하면 다시 움직이지 않고 바로 탈출이라고 합니다.
문제풀이는 다음과 같습니다.
(1) (생각)
묘지의 그리드 수는 W*H 개 입니다. (0,0), (1,0) , ... , (W-1, H-1) 에 각각 0, 1, ..., W*H-1 의 index를 붙여주어 생각할 것입니다. (x,y) 의 index 는 y*W+x 입니다.
( 고등학교에서 흔히 썼듯이 x축을 column으로(가로) y축을 row으로(세로) 생각해주었습니다. )
(2) (코드 36~66)
index 붙인 각각의 칸 (i,j)에서 움직일 수 있는 <칸, 걸리는 시간>을 vector배열로 저장했습니다.
(3) (코드 67~80)
밸만포드 구현입니다. 'dist[k]: index=0 (=입구 칸 (0,0)) 에서 index=k 칸으로 이동하는데 걸리는 시간' 으로 설정했습니다. 초기 dist[0]=0이고 나머지는 Infimum입니다.
과정(2) 에서 만들어 놓은 각 칸 별로 <이동할 칸, 걸리는 시간>을 갖고 밸만포드 돌립니다. 이과정에서 minuscycle 이 있는지 찾아줍니다.
안녕하세요 50퍼센트에서 정말 오랜 시간 계속해서 틀리다가. 작성자님 글 보고 도움 받아 해결했습니다. 정말 정말 정말 감사드립니다..
답글삭제제가 놓쳤던건 바로 마지막 코드 72번째 줄의 if(dist[i]==INF) continue; 부분입니다.
작성자님의 코드를 읽고 저 부분이 왜 필요할까.. 저 나름대로 생각해봤지만, 아직 벨만-포드 알고리즘에 익숙치 않아, 확실히 하고자 이렇게 질문드립니다.
저는 이 부분이 존재하는 이유가 사이클에 빠지거나, 묘비로 막히는 등의 이유로 정상적인 루트로는 도착하지 못 하는 지점에서도 완화작용이 일어나게 되는 것을
막아주기 위해서 넣었다고 생각하는데, 혹시 이 생각이 맞나요?
만약에 맞다면, 벨만-포드 알고리즘에서는 어떠한 이유로 도착하지 못 하게 되는 지점에 대해, 완화작업이 일어나지 않도록 항상 처리해주어야 하나요?
답변부탁드립니다. 좋은 글 감사합니다.
tmi : 저도 마포에서 학교를 다니는 전자전기공학과 학생입니다 깔깔