codingismylife   1년 전

while (!ladder[i][j - 1] && !ladder[i][j + 1])

i++;

이 코드 빼고 짰더니 시간이 800ms가 넘게 나와서, 다른 분들 코드와 비교하니까 이 코드 하나 차이로 시간이 엄청 절약되더군요!!


기존 백트래킹에서 continue로 조건 설정하는 거는 익숙해서 넘어갔는데, 

이 while문은 다시 이전 상태로 되돌아갈 때, 탐색 시간을 줄이기 위해서 넣은 건지 이해가 잘 안됩니다....

zenith82114   1년 전

어떤 i, j에 대하여 L45 if가 false가 되어 지나치고 DFS 재귀호출을 갔다가 되돌아온 상태를 생각해봅시다. 이때 L50 while이 참이라면 현재 세로줄 i에 j와 j+1 모두 사다리가 없다는 뜻으로, 이곳에 사다리를 놓았을 때 최적해는 방금 갔다 온 재귀호출의 최적해와 똑같습니다. 이런 세로줄들을 건너뛰는 최적화입니다.

codingismylife   1년 전

감사합니다!! 이 문제를 계기로 백트래킹에 대한 이해를 높이고 더 찾아보게 된 것 같습니다 ㅎㅎ 

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