[알고특] backtracking

대학생 알고리즘 특강을 들으며 백트래킹이라는 구현방법을 처음 알게되었다.

백트래킹은 나무위키에서 아래와같이 설명한다.

 

모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 

이 백트래킹을 사용한 대표적인 문제는 스도쿠이다.

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

2580번: 스도쿠

 

이 문제에서 한번은 런타임에러...2번은 틀렸다고 나왔다.

런타임에러는 class 이름을 Main이 아니라 Solution으로 해서 에러가 났었는데, 

2번 틀린게...처음에 왜 틀렸는지 이해가 안 갔다. 

그러다가 백트래킹을 알게되었고 해당 코드를 추가하며 해결되었다.

        //만약 0(값 비어있음)일 경우
        if(maps[r][c] == 0){
            for(int i =1; i<=9; i++){
                if(possible(r,c,i)){
                    maps[r][c] = i;
                    sdoku(r,c+1);
                }
            }
            maps[r][c] = 0;
            return;
        }
        sdoku(r,c+1);
    }

1. 어떻게 풀것인지

2. 시간복잡도

3. 공간복잡도

4. 핵심부분