amjong   5년 전

제가 푼 코드는 시간 짧게 나온 분들의 코드 푸는 방식과 거의 비슷한데 차이점이,

다른분들은 visited라는 알파벳 방문 체크용 배열을 전역 변수로 두고,

현재 지점에서 상하좌우 갈 수 있는 방향을 visited 배열과 현재 지점의 인덱스로 판단해서

갈 수 있으면 visited에 해당 알파벳을 방문표시 해주고, 호출 한 뒤에 다시 미방문표시를 해줍니다.(일명 백트래킹)

저는 밑 코드처럼 visited를 전역 배열로 두지 않고

그냥 int형 매개변수로 두고, 알파벳 수가 총 26개니까 비트마스킹으로 방문한 알파벳을 표시하여

(A : 0 ~ Z : 25)

매개변수로 전달했습니다. 

그리고 더이상 이동할 칸이 없을 시에는 매개변수로 받은 visited를 검사하여 몇 개의 알파벳을 방문했는지를 체크하고,

최댓값을 구했습니다.

보니까 함수 호출횟수는 같은 것 같던데(어쨌거나 모든 경로를 탐색하는 건 같음)

시간차이가 이렇게까지 많이 날 이유가 있나요? 궁금합니다ㅠㅠ.

아 참고로 제 코드는 1112ms, 제가 다른분들의 코드를 보고 고쳐서 냈을때는 520ms였습니다.

djm03178   5년 전

"그리고 더이상 이동할 칸이 없을 시에는 매개변수로 받은 visited를 검사하여 몇 개의 알파벳을 방문했는지를 체크하고,"

이 부분 때문에 느립니다. 함수 인자에 지금까지 방문한 알파벳의 수를 같이 전달하면 함수 호출 시마다 4방향 이동 + 1번의 체크만 있으면 충분한데, 이렇게 매번 개수를 처음부터 다시 센다면 함수 호출 시마다 4방향 이동 + 26번의 루프로 체크를 해야 하기 때문에 훨씬 많은 시간이 걸립니다.

amjong   5년 전

정말 감사합니다!! 말씀해주신 대로 함수 인자에 지금까지 방문한 알파벳의 수를 같이 전달하는 식으로 고쳐서 돌려봤더니 다른분들 코드보다 더 빠른 480ms 나오네요..

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