[백준/백트래킹] 2580번 스도쿠

이게 초등부 문제라는게 ... 참 대단한것 같다.

우선 스도쿠가 무엇인지는 문제에 나와있으니까 쉽게 이해할수있을거라고 생각한다.

우선 빨간색 부분이 비어있을때 형광펜으로 칠해진 부분에서는 절대 같은 숫자가 나와서는 안되는것이 스도쿠의 규칙이다.

나는 처음에, 빨간색 부분에 여러개의 숫자가 올 수 있다는것을 놓친 상태에서 그냥 단순 반복문으로 형광색으로 칠해진 부분에 없는 숫자가 무엇인지 찾아서 그 숫자를 빨간 부분에 박아 넣었다.

이렇게 하니까 당연히 틀렸다. 문제를 잘 못 이해한것이다.

빨간색 부분에 여러개의 숫자가 올 수 있다는것을 알게 되었고 이 문제는 결국 dfs를 활용한 완전 탐색 문제구나라는 생각이 들었다. 왜냐면 이런 빨간색 부분이 전체 판에 여러개가 있을 수 있고 각 빨간색 부분은 여러개의 숫자가 올 수 있기 때문에 결국에는 모든 경우에 대해서 다 숫자를 하나하나 넣어봐야 하기 때문이다.

첫번째로 판에 있는 모든 빨간색 부분에 대해서 각 빨간색 부분에 올 수 있는 숫자를 2차원 벡터에 저장하였다.

vector<vector<Pair>> 라는 2차원 벡터인데, Pair라는것은 빨간색 부분의 좌표와 그 빨간색 부분에 들어갈 수 있는 숫자를 가지는 구조체이다.

예를 들어 0,0에 숫자 3와 5가 들어갈 수 있다 

또한 1,1에 숫자 2와 9 8 7이 들어갈 수 있다 하면 아래와 같은 그림이 그려 질 것이다.

그리고 이 2차원 벡터를 순회하면서 각 좌표에 들어갈수 있는 숫자를 하나씩 넣어보고 isOk라는 함수로 형광부분을 한번더 체크하여 그 좌표에 숫자를 넣었을때 문제가 발생하는지 아닌지를 판단하게 된다.

문제가 발생할 경우 그 깊이로는 더이상 탐색해봐야 의미가 없으므로 프루닝(가지치기,더이상 깊이들어가지않음)을 할 수 있게 된다.

이런식으로 백트래킹을 활용한 dfs로 문제를 풀었다.