1. for문의 순서
*2로 이동하는걸 가장 먼저하는건 당연합니다. 비용이 0이기 때문이죠
각 칸마다 비용을 비교하며 최신화 해도 되지만, 그럴필요가 없이, 2배 이동을 가장 먼저 해서 자리 잡아두는 용도로 생각해도 됩니다
그리고 -1이 +1보다 먼저 하는것은, -1 이동 후 *2 이동을 했을 때, 먼저 도착하는 경우가 있어서입니다
4 6 예시를 보면, 4 >> 3 >> 6 비용 1이 최소이지만, 더하기부터 넣는다면 4 >> 5 >> 6 비용 2가 나옵니다
2. appendleft
1번에서 이어지는 내용인데, 비용 0인 *2연산을 최우선적으로 처리하기 위함이고, 0-1BFS의 핵심 아이디어 입니다. 0-1BFS관련 내용은 찾아보면 많이 나와요
10 14 예시를 생각해보면, 10 > 9 >> 8 >> 7 >> 14 비용 3, 10 >> 11 >> 12 >> 13 >> 14 비용 4
두 경우 모두 이동은 4번이지만, *2 연산으로 더 적은 비용의 이동 방법이 생기게 됩니다
1에서 말했던 것처럼, 각 장소마다 값의 크기를 계속 비교/최신화를 한다면 상관없겠지만, 더욱 간단한 알고리즘으로도 해결할 수 있어서 appendleft를 사용합니다
hashin0602 2년 전
코드에 써놓은 거처럼 for문에서 다른건 다 똑같고 2*x ,x+1, x-1로 하면 틀리고 2*x,x-1,x+1하면 정답으로 나옵니다. 이유가 뭔지 궁금합니다. 또 for문에서의 순서에 상관없다고 할때, i=2*x일때 q에 왜 appendleft를 하면 정답으로 처리되는지도 궁금합니다. 먼저 처리하게 하는지도 궁금합니다. 그냥 똑같이 처리해도 같은 결과값을 나오는거 아닌가요? 만약 두번째 appendleft를 사용하지 않았을때에는if 0 <= i < MAX: { if arr[i]==-1 or arr[i]==arr[x]+1 }이라고 추가로 해서 했었습니다.