정올 Q1824 스도쿠
문제 http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030
백트레킹
백트레킹이란 단어가 어렵게 느껴질 수 있지만 간단하게 말하면 모든 경우의 수를 다 확인하는 것으로 더 효율적인 방법으로 수행하는 것이다. 대표적 예로 DFS가 있다. (DFS, BFS는 차후 다룰 것이다.)
단계별로 수행과정을 살펴보자.
1. 한 단계를 변화시킬 경우의 수를 찾는다.
2. 그 중 한개를 선택한다.(순서는 임의로 선택한다.)
3. 선택된 경우에 수에서 1 단계와 마찬가지로 가능한 경우의 수를 찾는다.
4. 위처럼 1,2번을 번갈아 가며 수행하고 중간에 경우의 수를 찾지 못하였을때 이전 단계로 돌아가 다음 경우의 수를 수행한다.
여기서 4번처럼 목표에 도달하지 못하였을때 이전 단계로 돌아가는 과정 때문에 백트레킹이라는 이름이 붙혔다고 생각된다. 위 단계가 이해되지 않는 다면 DFS를 공부해보는 것을 추천한다.
그리디 알고리즘의 경우 현재에서 최선을 판단해 수행하지만 그것이 항상 답이라는 것을 보장받기 힘들다 이에 반해 백트래킹의 경우 모든 경우의 수를 수행한다는 점에서 최선의 답을 도출할 수 있지만 속도가 느리다는 단점이 있다.
고려사항
1. 가로선에 1~9까지 숫자중 하나만 들어간다.
2. 세로선에 1~9까지 숫자중 하나만 들어간다.
3. 사각형 안에 1~9까지 숫자중 하나만 들어간다.
4. 모두 0인경우가 존재할 수 있다.
문제 풀이
DFS는 스택을 사용하지만 스택 대신 재귀함수를 사용하여 문제를 해결하였다. 재귀도 스택도 같은 모양이니 편한데로 푸는것이 좋을듯 하다.
1. 입력을 받으며 빈곳의 위치를 배열에 저장한다.
위 맵의 경우 (0,0), (1,4), (1,7), (2,0)....이 저장될 것이다.
2. 배열에 저장된 순서대로 경우의 수를 확인한다.
2-1 (0,0)에 들어갈 수 있는 수를 확인한다. [1] 가능
2-2 (1,4)에 들어갈 수 있는 수를 확인한다. [3] 가능
.
.
.
3. 경우의 수가 2개 이상인경우 순서대로 실행한다.
4. 경우의 수가 없는 경우 이전단계로 돌아가 다음 경우의 수를 선택한다. Stack이나 재귀를 통해 가능
