[BOJ] 백준 2580 스도쿠 (Swift)

문제

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

풀이

스도쿠 판을 모두 채우는 문제입니다.
백트래킹 알고리즘을 사용해서 풀이할 수 있습니다.

먼저, 스도쿠 판에 0이 쓰여있는 좌표를 저장해줍시다.

이제 0이 쓰여있는 좌표에 1부터 9까지 수를 하나씩 대입해보고,

대입한 수가 가로줄, 세로줄에 쓰여있으면 안되고, 또한 3x3 정사각형에도 쓰여있으면 안됩니다.
이것을 확인해줄 함수를 작성해주었습니다.

가로줄은 y좌표에서 1부터 9까지의 x좌표 중 이미 쓰여있는 수가 있는지 확인을 해주었습니다.
세로줄은 x좌표에서 1부터 9까지의 y좌표 중 이미 쓰여있는 수가 있는지 확인을 해주었습니다.

마지막으로 3x3 정사각형에서 검사를 어디서부터 시작해야할지를 구해줬습니다.
현재 y, x좌표에서 3으로 나누고 다시 3을 곱해준다면 그 좌표가 정사각형의 시작점일 것입니다.

예를 들어 (2, 5)를 감싸는 3x3 정사각형의 시작점은 (2 / 3 * 3 = 0, 5 / 3 * 3 = 3) 이므로 (0, 3)이 됩니다.

이제 시작점에서 x로 3만큼, y로 3만큼 중에서 이미 쓰여있는 수가 있는지 확인을 해주었습니다.

모두 확인했다면 그 수는 일단은 적을 수 있는 수 이므로 작성해줍니다.

이후, 0이 쓰여있는 다른 좌표에서도 이 작업을 반복하고, 만약 1 ~ 9까지의 모든 수를 작성할 수가 없는 경우에는
이전에 썼던 수를 지우고 다른 수를 써주는 백트래킹 작업이 필요합니다.

모든 수를 썻다면 exit 메서드로 프로그램을 종료하였습니다.

소스코드

후기

맨 처음 풀 때는 조금 어려웠지만, 이미 쓰여있는 수인지의 조건을 잘 나누어서 풀이할 수 있었습니다.
재미있었던 문제였습니다.