amel   4년 전

https://www.acmicpc.net/problem/1840 에 올린 데이터 추가 요청글 https://www.acmicpc.net/board/view/87250 에서 볼 수 있듯이 별 생각없는 단순한 백트랙킹으로는 스도쿠를 해결하는데 오래 걸립니다.


아래 반례를 보면 좌상단에 1, 2를 채우면 해결할 수 없습니다. 4, 5행의 '1'과 1열의 '1'이 있으면 왼쪽 중간 박스에는 '1'이 들어갈 자리가 없기 때문입니다. (4~6행, 1~3열 박스)

따라서 좌상단에는 반드시 2, 1로 채워야 합니다. 만일 1, 2로 채운 경우 이것이 안된다는 것을 알려면 사이의 '0'을 1~9로 모두 채워봐야만 합니다.

보통의 코드들은 칸을 1부터 순차적으로 채우기 때문에 시간 초과를 받습니다. (제 코드 포함) 대충 구글링해본 풀이들은 싹다 시간초과 나는듯 합니다.

amel   4년 전

저도 그렇게 생각했긴 한데, 0ms 나온 분들 코드를 보면 역시 백트랙킹으로 푸셨습니다. 방법이 조금 다르지만요. 이런 코드들은 저 반례도 잘 돌아가고, 그런 풀이가 골드급의 백트랙킹을 벗어나는 것 같지는 않습니다.

djm03178   4년 전

이 문제는 처음부터 설계가 '좌상단부터 차례대로 1~9를 채우는 백트래킹'을 정해 풀이로 하여 만들어지지 않았나 생각합니다. 출제자들이 요구하던 수준 이상의 데이터는 애시당초 염두에 두지 않았을 것입니다. 그보다 더 효율적인 백트래킹을 구현해야 풀 수 있는 문제가 되면 그 시점에서 이미 문제의 의도를 넘어선 것이라고 보입니다.

startlink   4년 전

수정했습니다.

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