[BOJ] 9663 - N-Queen

사용 언어: Python3

문제

백준 9663

문제 풀이 핵심 아이디어

• N X N 크기의 체스 보드 위에 퀸 N개를 서로 공격할 수 없게 배치시켜야 합니다.
• 대표적인 백트래킹(Backtracking) 문제입니다.
  • 백트래킹이란, 가능한 경우를 전부 탐색하면서 더이상 나아갈 수 없는 경우를 만났을 때
    이전으로 돌아가서 다른 경우를 선택하는 문제 유형입니다.
• N=4일 때는, 다음과 같은 경우가 존재합니다.
  
• DFS를 이용하여 간단히 백트래킹 알고리즘을 구현할 수 있습니다.

내 풀이

첫 번째

N = 8
B = [[0 for _ in range(N)] for _ in range(N)] # 1이면 퀸을 놓은 것
ck = [[0 for _ in range(N)] for _ in range(N)] # 퀸을 놓을 수 있는 칸은 0, 없는 칸은 1로 표시

# 자기자신, 대각선 포함 반시계방향
dx = [0,0,-1,-1,-1,0,1,1,1]
dy = [0,1,1,0,-1,-1,-1,0,1]
def updateCk(x,y):
  # 자기 자신
  xx = x + dx[0]
  yy = y + dy[0]
  ck[xx][yy] = 1
  # 대각선 포함 반시계방향
  for w in range(1, 9):
    tmp = 1
    while True:
      xx = x + dx[w]*tmp
      yy = y + dy[w]*tmp
      if xx < 0 or xx > N-1 or yy < 0 or yy > N-1:
        break
      ck[xx][yy] = 1
      tmp += 1

def dfs():
  for i in range(N):
    for j in range(N):
      if ck[i][j] == 1:
        continue
      updateCk(i,j)
  dfs()

# updateCk(2,1)
      
# output
for row in ck:
  for val in row:
    print(val, end=" ")
  print()

다른 사람 풀이

백트래킹

N = int(input())
row = [0] * N # row[x] = i -> x행 i열에 퀸이 있다.

# x번째 행에 놓은 퀸에 대해서 검증
def check(x):
  # 이전 행에서 놓았던 모든 퀸들을 확인
  for i in range(x):
    # 위쪽 혹은 대각선을 확인
    if row[x] == row[i] or abs(row[x]-row[i]) == x-i: # x축 차이와 y축 차이가 같다면 같은 대각선에 있다는 것
      return False
  return True

# x번째 행에 대하여 처리
def dfs(x):
  global cnt
  if x == N:
    cnt += 1
  # 아직 탐색할 row가 남음
  else:
    # 해당 row의 1~N열 칸을 탐색
    for i in range(N):
      row[x] = i # x행, i열에 퀸을 둔다고 가정
      if check(x): # 해당 칸이 다른 퀸이 겹치지 않는지 판별
        dfs(x+1) # 겹치지 않으면 다음 행으로 넘어가기


cnt = 0
dfs(0)
print(cnt)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기