Recursion의 응용 - n queens
가로세로 크기가 N인 2차원 배열(체스판)이 주어진다
이 체스판에 N개의 말을 놓는데, 그중에 어떤 2개의 말도 동일한 행이나 열, 대각선에
오지 않게 배치하는것이 n queens 문제이다.
가장 기본적으로 생각 되는것은
동일한 행, 열에 배치가 되지 않으므로 한 행, 열당 1개의 말을 배치할수 있다는 것이다
행을 기준으로 생각해 봤을때
1개의 행에 놓일수 있는 경우의 수는 4 가지이다.
따라서, 1개의 행에 하나씩 놓으며 그것이 해가 아닐경우 체스말을 치우고
바로 전의 행으로 돌아와 다른 경우의 수를 살핀다.
이와 같은 방법을 backtracking이라고 한다.
backtracking은 자신이 지나온 궤적을 되돌아온다는 것이다
즉, 어떠한 결정을 내리다가 안된다는 것이 분명해지면
자신이 최근에 내린 결정을 번복하고 뒤로 돌아가 다른 경우를 살펴보는 것이다.
이 과정을 조금 더 체계적이고 시각적으로 가시화 하기위해
일반적으로 상태공간트리라는 것을 사용한다.
가장 위의 root가 시작일 때 각각의 경우에 따라 4개씩 경우의 수가 분화한다.
실제로 이와 같은 트리를 다 그린다면,
체스판에 말을 놓을 수 있는 경우를 모두 나열하는 것 이므로
우리가 해를 찾는다면 그 해는 반드시 이 상태공간트리 안에 있을것이다.
다른 말로, 어떤식으로든 이 트리의 모든 노드를 방문한다면
해를 찾을수 있다는 것이다.
물론 이러한 트리를 실제로 그리거나, 데이터 구조로 만든다는 뜻은 아니다
상태공간트리는 개념적이고 논리적인 것이다.
실제로는 이 트리를 탐색하는 코드를 만드는 것이다.
또한 모든 노드를 탐색하지도 않는다.
그 뜻은 다음과 같다.
방금 전 살펴본 backtracking의 방법으로 탐색을 진행했을 경우
답으로써의 가능성이 보이지 않는 노드의 하위 노드를 방문하지 않아도 되기때문이다.
이렇게 해가 아님이 자명한 노드를 non-promising, 또는 infeasible 하다 라고한다.
이렇게 infeasible한 노드를 만날경우 되돌아오는 backtracking기법으로
해를 찾을 경우 탐색의 경로는 위와 같다.
이와 같은 탐색의 방법을 깊이우선 탐색(DFS-Depth First Search)이라고 하며
유명한 트리의 탐색 기법중 하나이다.
이러한 깊이 우선 탐색은 스택과 Recursion을 이용해서 구현할수 있다.
그중 Recursion이 더욱 쉽고 간명하게 표현할 수 있는 장점이 있다.
1 2 3 4 5 6 7 8 | return-type queens(argument){ if non-promising report failure and return else if success report answer and return else visit children recursively } | cs |
이를 슈도 코드로 구현 했을 때
먼저, 현재 자신의 노드가 non-promising, 즉, 꽝인가를 검사한다.
두번째로, 현재 도착한 노드가 답인지를 검사한다.
만약 그렇다면 일반적으로 답을 출력하고 return을 한다.
마지막으로, 꽝도 아니고 최종적인 답도 아니라면
이 노드 밑의 자식 노드들을 순서대로 방문하는 것이다.
1 2 3 4 5 6 7 8 9 | int [] cols = new int[N+1] return-type queens(int level){ if non-promising report failure and return else if success report answer and return else visit children recursively } | cs |
그렇다면 이 함수에 어떤 매개변수를 전달 해야할까?
자신이 노드에 도착했을때 어떤 노드인지 판별할 수 있는지를
판별할수 있는 값을 전달해야한다.
따라서 1개의 전역 변수 cols와 1개의 매개변수를 가지고 판별을 하도록 한다.
매개변수로 전달된 level은 트리상에서의 레벨, 체스판에서 행을 나타낸다.
말이 놓인 위치를 표현하기 위해서 2차열 배열이 필요하지 않다
어차피 1번말은 1번행에 놓이고 2번말은 2번행에 놓이기 때문이다.
따라서 level개의 말이 어디에 놓인지 판별하기 위해서는 1차원 배열만 필요하다.
1번부터 level번까지의 말이 어디에 놓였다는 것을 cols라는 배열에 저장된다
따라서 cols는 열번호를 나타낸다.
함수를 통해 cols[1]에서 cols[level]까지의 경우의 수를 탐색한다.
1 2 3 4 5 6 7 8 9 | int [] cols = new int[N+1] boolean queens(int level){ if (!promising(level)) return false; else if (level==N) return true; else visit children recursively } | cs |
그리고 리턴형은 추후에 바뀌더라도 boolean으로 설정한다.
즉, yes와 no로 판별한다는 것이다.
조건식의 첫번째는 promising한 것이 아닐때
리턴 타입에 맞추어 false를 리턴한다
두번째는 배열의 끝, 트리의 마지막 노드에 도달 했을때 이다.
그리고 non-promisiong은 통과하지 않으므로 level이 N과 같다는것은
모든 조건을 통과하고 체스판에 끝까지 말이 놓여졌다는 의미이다
따라서 조건을 만족할 경우 true를 리턴한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int [] cols = new int[N+1] boolean queens(int level){ if (!promising(level)) return false; else if (level==N) return true; else for(int i=1; i<=N; i++){ cols[level+1] = i; if(queens(level+1)) return true; } return false; } } | cs |
마지막으로 어느것이도 해당하지 않을 때 조건이다
for문을 이용해서 level+1, 자신이 있는 체스판 다음행에서 첫번째 열에 체스말을 둔다.
그리고 재귀 함수를 호출해서 참, 거짓을 판별한다.
참일 경우 즉시 true를 리턴하며 함수는 종료된다.
그렇지 않은 경우 i+1, 다음 열에 체스말을 두고
재귀 함수를 호출해서 참, 거짓을 판별한다.
모든 열에 해가 없을경우는 for문을 탈출하고 false가 리턴된다.
1 2 3 4 5 6 7 8 9 | boolean promising(int level){ for(int i = 1; i<level; i++){ if(cols[i]==cols[level]) return false; else if on the same diagonal return false; } return true; } | cs |
마지막으로 남은것은 pomising test를 코드로 구체화 시키는 것이다.
그런데 조건을 잘 살펴보면 다음과 같은 것을 발견할 수 있다.
현재 말이 4개가 놓여있다면 앞에 3개의 말에는 어차피 충돌이 없다는 것이다.
앞에서 충돌이 있다면 non-promision으로 판별되어 내려오지 않기 때문이다.
즉, 하나를 제외한 앞쪽 level-1개의 말들은 서로간의 충돌이 없음이 보장되어있으므로
마지막 말이 앞쪽의 말들과 충돌이 없음을 판별하면 된다.
우선 위와 같이 별도의 promising 체크 함수를 만든다
for 문을 돌면서 체크하는데, 첫번째 조건은 같은 열에 있을 경우를 체크한다.
두번째 조건은 같은 대각선에 있을 경우를 체크한다.
대각선은 어떻게 체크하면 될까?
대각선에 놓여있다는 것은 cols[level]-cols[i]와 level-i의 길이가 같음을 나타낸다.
크기가 커서 반대인 경우도 있으므로 절대값을 씌워주도록 한다.
level-i = |cols[level]-cols[i]|
1 2 3 4 5 6 7 8 9 | boolean promising(int level){ for(int i = 1; i<level; i++){ if(cols[i]==cols[level]) return false; else if (level-i == Math.abs(cols[level-cols[i]])) return false; } return true; } | cs |
결과적으로, 다음과 같은 코드로 나타낼수 있으며
이를 이용해서 n-queens 문제를 풀어낼 수 있다.
(초기 호출은 queen(0)으로 한다.)
출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘
'알고리즘 문제풀이' 카테고리의 다른 글
| [알고리즘] Sort - 기본적인 정렬 알고리즘(선택,삽입,버블) (0) | 2017.04.19 |
|---|---|
| [알고리즘] Recursion의 응용 - 멱집합(power set) (0) | 2017.04.19 |
| [알고리즘] Recursion의 응용 - Counting Cells in a Blob (0) | 2017.04.18 |
| [알고리즘] Recursion의 응용 - 미로찾기 (0) | 2017.04.18 |
| [알고리즘] Recursion 이란 - 3 (0) | 2017.04.18 |
댓글