Java) BOJ 2580. 스도쿠
문제 링크
제한
- 시간 제한 : 1 초
- 메모리 제한 : 256 MB
문제
-
스도쿠는 18세기 스위스 수학자가 만든 ‘라틴 사각형’이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
-
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
-
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
- 아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
-
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
-
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
👀 풀이
- 처음엔 for문을 여러번 돌려서 n^3에 가깝게 풀었는데 그래서 그런지 시간 초과가 났다…
-
그래서 시간을 줄여보려고 입력 받으면서 0인 칸만 따로 저장한 뒤 거기만 탐색하는 방식으로도 해 봤지만 역시 1%에서 시간초과가 나서 질문 게시판과 구글링을 참고했다.
- 스도쿠의 가로세로줄과 3*3 칸을 검사한 뒤 겹치는 숫자가 없도록 넣어야 하기 때문에 이것을 검사하는 함수를 만들어서 0인 위치에 대해서 1~9 까지의 숫자를 넣어서 검사를 실시한 뒤 해당 숫자를 넣을 수 있으면 수를 삽입한 뒤 스도쿠에 숫자를 넣는 함수를 재귀호출한다.
- 스도쿠 칸을 채우는 방법이 여러 개가 있을 수 있기 때문에 보드판이 다 채워지는대로 보드판을 출력하고 System.exit(0)을 사용해서 프로그램을 종료한다.
결과
- 시간 : 672 ms
- 메모리 : 28336 KB