[C++] 백준 2580번 스도쿠

2580번: 스도쿠

백트래킹 문제.

골드 4문제였는데 생각보다 너무 쉽게 풀렸다.

백트래킹 알고리즘을 사용해서 그런건가?

백준의 티어는 정말 알 수가 없다. 어떤 문제는 실버문제여도 오래 붙들고 있어도 안풀리는데,

이런 문제는 금방금방 쉽게 풀린다.

근데 또 정답률은 낮다...흠...

나도 사실 정사각형 3x3 고려를 하지 못해서 틀렸었다.

아마 나도 운이 좋아서 시간초과에 안걸려서 맞춘 것일 수도 있을 것 같다.

 

문제풀이

스도쿠게임을 완성시키돼, 백트래킹 알고리즘을 사용해서 구현하면 된다.

고려해 줄 사항은 다음과 같다.

1. 내가 넣은 숫자가 세로줄에 같은 것이 있나? 있다면 return
2. 내가 넣은 숫자가 가로줄에 같은 것이 있나? 있다면 return
3. 내가 넣은 숫자가 3x3 사각형에 같은 것이 있나? 있다면 return

이 세가지만 고려해주고 보드판을 완성시킨 후, 출력하고 종료시키면 된다.

 

바로 코드를 살펴보자.

 

사용한 STL과 변수

vector를 사용해서 빈 공간의 좌표들을 벡터에 넣어놓는다.

그리고 스도쿠 판인 board 2차원 배열을 사용했다.

 

백트래킹 메서드 - 1

백트래킹 메서드는 다음과 같은 구조이다.

우선 매개변수 idx는 판에서 몇번째 숫자를 넣는 중인지 구하는 것이다.

그리고 prevYPoint와 prevXPoint는 수를 삽입한 좌표이다.

해당 좌표에 수가 적절하게 잘 들어간 것인지 체크하기 위해 매개변수로 받아놓는다.

 

1. addNum 변수에 현재 메서드에 들어오기 전에 어떤 수가 들어갔는지 저장한다.

2. for 반복문을 돌려서 가로, 세로에 같은 수가 있는지 확인한다. 만일 중복되는 수가 있다면 return한다.

 

그리고 3x3 사각형을 체크하기위한 좌표를 새로구한다.

O (1, 1)			O(1, 4)			O(1, 7)
O(4, 1)			O(4, 4)			O(4, 7)
O(7, 1)			O(7, 4)			O(7, 7)

동그라미 쳐놓은 좌표에서 3x3으로 확인하면 된다.

그렇다면 내가 넣은 좌표가 어디에 속하는지는 어떻게 표현할까?

X 또는 Y좌표가 1부터 시작한다고 할 때

좌표가 4보다 작다면 1, 4보다 크고 7보다 작다면 4, 7보다 크거나 같다면 7로 좌표를 설정해주면 된다.

어차피 이렇게 좌표를 설정하면 어차피 해당 좌표가 3x3범위에 들어가게 되기 때문이다.

 

후에 3x3 체크시작 좌표와 수를 넣은 좌표를 매개변수로 넣고 3x3 사각형 체크 메서드를 실행한다.

3x3 사각형 체크 메서드

3x3 사각형에 좌표에 넣은 수와 같은 수가 있는지 체크한다. 만일 있다면 false를 return하고

없다면 true를 return하도록 만들었다.

 

백트래킹 메서드 - 2

다시 백트래킹 메서드로 돌아와서 설명하자면

 

idx, 내가 지금 몇 번째를 찾는지에 대한 매개변수가 빈 칸의 개수보다 많다면 조건을 만족하고

스도쿠 판을 완성시킨 것이므로, 스도쿠 판을 출력한 후에 exit(0) 함수로 프로그램을 종료시킨다.

 

만일 아직 채워야할 빈 공간이 남아있다면, idx - 1번째에 있는 빈 공간에 대해서 찾아준다. idx - 1을 한 이유는

vector는 0번째부터 시작하기 때문이다.(ex. 2번째 빈 공간은 vector[1]에 있다.)

이렇게 백트래킹을 1 ~ 9 까지 넣어보며 반복적으로 진행하며 스도쿠 판을 채워준다.

 

메인함수

메인함수에서는 각 스도쿠 판의 정보를 입력받는데, 0인 경우에는 빈 공간을 담는 벡터에 좌표를 입력해 놓는다.

그리고 빈 공간 첫번째의 좌표로 1 ~ 9까지 넣어보며 백트래킹을 시작해본다.

 

처음에 3 x 3 사각형을 고려하지 않아서 한 번 틀렸었다.

고려해주니 쉽게 맞출 수 있었던 문제.

시간을 좀 더 줄여볼까 생각해봤지만 지금상태로는 쉽지 않을 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인이 가능하다.