[백준/Python]9663: N-Queen

문제

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

백준 단계별 풀이 - 백트래킹

---

풀이

기준이 바뀐것인지 일반적인 코드로는 통과되지 않았다.
결국 비트마스킹을 이용한 풀이로 성공...

# 1
def dfs(row, ld, rd, n):
    if row == all_bits:
        return 1

    count = 0
    poss = all_bits & ~(row | ld | rd)

    while poss:
        bit = poss & -poss
        poss -= bit
        count += dfs(row | bit, (ld | bit) << 1, (rd | bit) >> 1, n)

    return count

# 2
N = int(open(0).readline())
all_bits = (1 << N) - 1
print(dfs(0, 0, 0, N))

• row: 현재 행
• ld, rd: 퀸의 왼쪽 대각선, 오른쪽 대각선
• poss: 가능한 열의 위치 파악 (ex: 0110 => 두번째, 세번째 열 가능)
• bit: 가능한 열 중 가장 오른쪽에 위치한 열 선택(모든 가능한 위치 순차적으로 순회 예정)
• count: 현재 상태에서 찾은 해답의 수

---

단계별 풀이

1. 함수 생성

def dfs(row, ld, rd, n):
    if row == all_bits:
        return 1

    count = 0
    # 1
    poss = all_bits & ~(row | ld | rd)  # row, ld, rd가 아닌 열 => 가능한 열

    # 2
    while poss:
        bit = poss & -poss
        # 3
        poss -= bit
        # 4
        count += dfs(row | bit, (ld | bit) << 1, (rd | bit) >> 1, n)

    return count

1. poss로 가능한 열을 체크한다.
   • (row | ld | rd)는 퀸들이 위치한 행, 퀸의 왼쪽/오른쪽 대각선을 뜻한다.
     이걸 ~를 통해 뒤집어주면 가능한 열의 위치가 된다.
   • all_bits를 통해 NxN의 크기로 한정한다.
2. poss가 존재하는 동안 아래의 행위를 반복한다.
   • poss & -poss: 가장 오른쪽의 1을 선택. (가능한 열의 위치 중 가장 오른쪽의 열을 선택)
   • poss가 1001이라 가정하면, -poss = 0111이 된다.
     AND연산으로 0001이 남게 되며, 가장 오른쪽의 열을 뜻한다.
3. 가능한 열의 위치에서 선택한 열의 위치(bit)를 제거.
4. dfs()에 다음 인자를 넣어주고, 그 값을 count에 추가한다.
   • row | bit: 퀸들의 위치값 row에 위치 bit 추가
   • (ld | bit) << 1: ld에 현재 퀸의 위치 bit를 추가한 뒤 왼쪽으로 1 시프트.(왼쪽으로 1열 이동)
   • (rd | bit) >> 1: 위와 같음.

 

2. 체스판 입력값 받기, 결과 출력

N = int(open(0).readline())
all_bits = (1 << N) - 1

• 먼저 체스판의 크기, 퀸의 갯수 N을 입력받는다.
• N의 크기만큼 1로 이루어진 이진 비트열을 생성해준다.
  • 만약 N = 4일때, 1 << N = 10000이 되고, 여기서 1을 빼줘 1111로 만들어준다.
• 0, 0, N을 인자값으로 함수를 실행시킨 뒤 값을 출력.