2239번 - 스도쿠
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부터 순차적으로 채우기 때문에 시간 초과를 받습니다. (제 코드 포함) 대충 구글링해본 풀이들은 싹다 시간초과 나는듯 합니다.
저도 그렇게 생각했긴 한데, 0ms 나온 분들 코드를 보면 역시 백트랙킹으로 푸셨습니다. 방법이 조금 다르지만요. 이런 코드들은 저 반례도 잘 돌아가고, 그런 풀이가 골드급의 백트랙킹을 벗어나는 것 같지는 않습니다.
이 문제는 처음부터 설계가 '좌상단부터 차례대로 1~9를 채우는 백트래킹'을 정해 풀이로 하여 만들어지지 않았나 생각합니다. 출제자들이 요구하던 수준 이상의 데이터는 애시당초 염두에 두지 않았을 것입니다. 그보다 더 효율적인 백트래킹을 구현해야 풀 수 있는 문제가 되면 그 시점에서 이미 문제의 의도를 넘어선 것이라고 보입니다.
수정했습니다.
댓글을 작성하려면 로그인해야 합니다.
amel 4년 전 2
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부터 순차적으로 채우기 때문에 시간 초과를 받습니다. (제 코드 포함) 대충 구글링해본 풀이들은 싹다 시간초과 나는듯 합니다.