[백준] 9663 N-Queen | Gol4 | 백트래킹 Python (시간초과)

[백준] 9663 N-Queen | Gol4 | 백트래킹 Python (시간초과)

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

 

백트래킹 연습으로 풀어본 문제.

돌고돌아서 테케가 통과되는 코드는 만들어냈지만 시간제한은 pypy로도 끝끝내 통과 못시킨 문제

통과된 코드들이랑 비교해서 고쳐도 봤는데, 아예 코드를 갈아엎어야 하는 것 같다

너무 시간을 많이 써서 여기까지만 하는 걸로.. 애초에 파이썬으로 통과되기 빡빡한 문제라고 하고,

내 수준에서는 최적화에 시간을 더 쓰기보다는 다른 문제들을 풀어보는 게 맞는 것 같다.

그래도 얻은 것들이 많아서 기록!

 

구상

 

[문제해석]

• N-Queen : 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
  • N이 주어지고, N개를 놓을 수 있는 경우의 개수를 구하기
  • 제한시간 : 10초 (뭐든 하라는 건가)
  • 퀸은 가로세로대각선 어느방향으로든 원하는 만큼 이동할 수 있음
        ->퀸 특성상 한 행에 여러개가 올 수 없으므로 NxN인 행에 N개를 두려면 무조건 각 행에 퀸이 한개씩 배치되어야 함

헤매기
처음에는 체스판(좌표)이라 당연히 2차원 배열로 해보려고 했는데 중복제거 등의 문제를 어떻게 해결해야 할지 막힘
점점 백트래킹과도 멀어지는 구상이 나와서 힌트 찾아봄
-> 2차원 좌표는 1차원 배열에도 저장할 수 있다!

 

• 구상
  • 배치한 퀸 좌표를 1차원 배열에 저장
  • 체스판 좌표마다 이미 배치된 퀸 목록 돌며 배치 가능한 좌표인지 확인(좌표값으로 계산)
    • TS : 체스판 좌표를 다 돌지 않아도 됨. 퀸 특징때문에 어차피 한 줄에 하나밖에 못놔서 행변호만 반복문 돌면 된다..
       -> 무조건 한 행에 한 퀸 배치! 다음 퀸은 다음 행에서 탐색
      해당 행에 퀸을 하나도 배치할 수 없는 경우 N개를 배치할 수 없다는 의미이므로 백트래킹 할 것!
      그리고 무조건 한 행에 퀸 하나씩이라 중복 없음
  • 배치 가능하면 배치 후 dfs재귀
  • 어디에도 배치 불가능하면 백트래킹
  • n개 모두 배치했으면 경우의 수 +1

 

트러블 슈팅

• 1차원 배열 솔루션
  • 2차원 배열 정보를 꼭 2차원에 담아야 하는 건 아님. 인덱스 자체를 정보로 쓸 수도 있음
  • (x,y) 좌표를 x=인덱스, y=값 으로 해서 그냥 리스트에 넣을 수도 있음
    -> 이러면 튜플로 바꿔서 set에 넣어 중복체크도 가능함 (but 이 문제에서는 상황상 중복체크가 필요없음..풀이 참고)
• TIP : 리스트 인덱스도 함께 반복문 돌고 싶을 떈 enumerate(리스트)

 

 

코드

# timeout : 백트래킹(시간초과)
# TS : 2차원 좌표는 1차원 배열에 저장할 수도 있다.
# TIP : 리스트 인덱스도 함께 반복문 돌고 싶을 떈 enumerate(리스트)

'''
[문제해석]
N-Queen : 크기가 NxN인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
- N이 주어지고, N개를 놓을 수 있는 경우의 개수를 구하기
- 제한시간 : 10초 (뭐든 하라는 건가)
** 퀸은 가로세로대각선 어느방향으로든 원하는 만큼 이동할 수 있음
    ->퀸 특성상 한 행에 여러개가 올 수 없으므로 NxN인 행에 N개를 두려면 무조건 각 행에 퀸이 한개씩 배치되어야 함

구상 3
- 배치한 퀸 좌표를 1차원 배열에 저장
- 체스판 좌표마다 이미 배치된 퀸 목록 돌며 배치 가능한 좌표인지 확인(좌표값으로 계산)
    - TS : 체스판 좌표를 다 돌지 않아도 됨. 퀸 특징때문에 어차피 한 줄에 하나밖에 못놔서 행변호만 반복문 돌면 된다..
        -> 무조건 한 행에 한 퀸 배치! 다음 퀸은 다음 행에서 탐색
            해당 행에 퀸을 하나도 배치할 수 없는 경우 N개를 배치할 수 없다는 의미이므로 백트래킹 할 것!
            그리고 무조건 한 행에 퀸 하나씩이라 중복 없음
- 배치 가능하면 배치 후 dfs재귀
- 어디에도 배치 불가능하면 백트래킹
- n개 모두 배치했으면 경우의 수 +1
'''

N = int(input())

board = [-1]*N # x=인덱스, y=값에 좌표 저장
result = 0

def dfs(q_cnt) :
    if q_cnt == N :
        global result
        result += 1
        return
    
    i = q_cnt #현재 q_cnt개의 퀸이 이미 배치되어있으므로 q_cnt+1번째 행, 즉 인덱스 q_cnt인 행에 이번 퀸을 배치해야 함
    for j in range(N) : #이번 행의 열을 돈다
        # 퀸 목록 돌며 배치 가능한지 확인
        able = True
        # for x, y in enumerate(board) : #시간 줄여보려고 enumerate 빼봄
        for idx in range(q_cnt) : #직전행까지만 퀸이 배치되어있을 것이므로 직전행까지만 확인하면 됨
            x, y = idx, board[idx]
            if j == y or abs(x-i) == abs(y-j) : #열, 대각선 중 하나에 걸림
                able = False
        
        #이 열번호에 배치 불가. 다음 위치 탐색
        if not able :
            continue
        
        #배치 가능
        board[q_cnt] = j
        dfs(q_cnt+1)
        # board[q_cnt] = -1

dfs(0)
            
print(result)

 

 

그만 붙잡고 보내준다 나중에 성장해서 다시 만나..~