컴퓨터 과학알고리즘

N-Queens Problem

⏱ 읽기 소요 시간: 20 분

이번에는 Recursion의 응용 - N-Queens Problem에 대해 알아봅시다.

본 포스팅은
<인프런 - 권오흠 강사님의 영리한 프로그래밍을 위한 알고리즘 강좌 > 자료를 인용하였음을 알려드립니다.

N-Queens Problem

  • 퀸 N개를 서로 공격할 수 없게 놓는다.

  • 퀸은 가로줄, 세로줄, 대각선으로 같은 줄에 놓을 수 없다.

되추적 기법(Backtracking)

: 상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘을 말한다.

Design Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
return-type queens(arguments) {
    // 아래의 코드는 어떤 노드에 딱 도착했을 때
    // 해야 할 일을 순서대로 기술한 것이다.

// 이미 말들이 충돌되어서 확인할 필요가 없는 노드인가?
// 꽝
// (이 노드 뿐만 아니라 밑으로 내려가서 확인할 필요가 없는 노드)일 경우
if non-promising
    // 즉시 되돌아 간다.
    report failure and return;
// 이 노드가 찾던 답이 되는 노드인가
else if success
    report answer and return;
// 꽝도 아니고, 답도 아니라면
else
    // 자식 노드들을 순환하며 방문한다.
    visit children recursively;
}
  • queens라는 함수가 여러 번 호출된다.
  • ‘이 함수가 호출되는 시기는 트리의 어떤 node에 딱 도착한 순간이다’라고 생각하면 된다.
  • 매개변수(arguments): 트리 상에서 내가 지금 도착한 노드가
    어떤 노드인지를 판별할 수 있는 정보가 이 매개변수로 들어올 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 지금 트리상에서 어떤 노드에 있는지
// 전역 변수인 cols와 매기변수인 level을 이용해서
// 함수 queens에 정보를 줄 수 있다.

int [] cols = new int [N+1];
// 이 문제에서 행번호는 필요 없다.
// cols[1]: 1번말이 놓인 열번호
// cols[2]: 2번말이 놓인 열번호
// ...
// cols[level]
return-type queens(int level) {
    if non-promising
        report failure and return;
    else if success
        report answer and return;
    else
        visit children recursively;
}
  • 매개변수 level은 현재 노드의 레벨을 표현한다.
  • cols[i] = j는 i번 말이 (i행, j열)에 놓였음을 의미한다.
1
2
3
4
5
6
7
8
9
int [] cols = new int [N+1];
boolean queens(int level) {
    if non-promising
        report failure and return;
    else if success
        report answer and return;
    else
        visit children recursively;
}
  • return-type은 일단 boolean으로 하자.
  • 즉, 성공인지 실패인지를 반환한다.
1
2
3
4
// 현재 도착한 이 노드가 꽝인지 아닌지를 판별해주는 함수 promising 있다고 가정하자.
if(!promising(level))
// 꽝이라면 false를 반환한다.
  return false;
  • 노드가 어떤 경우에 non-promising할까?
  • 일단 이 문제는 나중에 생각하자.
1
2
3
4
5
6
// 이 코드는 위의 promising 테스트를 통과해야만 도달할 수 있는 코드이다.
// level이 N이라는 것은 어쨌든 모든 말이 다 놓였다는 의미
//-> 놓인 말들 사이에 충돌이 없다는 의미

else if (level == N)
    return true;
  • promising 테스트를 통과했다는 가정하에 level == N이면,
    모든 말이 놓였다는 의미이고 따라서 성공이다.
1
2
3
4
5
for(int i=1 i <= N; i++) {
    cols[level+1] = i;
    if(queens(level+1))
        return true;
}
  • level+1 번째 말을 각각의 열에 놓은 후, recursion을 호출한다.

Promising Test

1
2
3
4
5
6
7
8
9
10
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;
    }
}

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;
    }
}
  • cols[i]와 cols[level] 중에 어떤 값이 큰지 모르기 때문에
    cols[level] - cols[i]에 절대값을 씌워준다.

정리

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int [] cols = new int [N+1];
boolean queens(int level) {
    // if non-promising
    //     report failure and return;
    if(!promising(level))
        return false;

    // else if success
    //   report answer and return;
    else if (level == N) {
        for(int i = 1; i <= N; i++) {
            System.out.println("(" + i + ", + " + cols[i] + ")");
        return true;
        }
    }

    // else
    //   visit children recursively;
    for(int i = 1; i <= N; i++) {
        cols[level + 1] = i;
        if(queens(level + 1))
            return true;
    }
    return false;
}
  • 처음에는 queens(0)으로 호출한다.
Share