프로그래머스 LV2 - N-퀸

문제 링크

내 풀이 (미해결)

# 퀸이 같은 행, 같은 열, 같은 대각선에 있을 경우 백트래킹
# 아예 놀 곳이 없을 경우 그 전에 거 이동
# 퀸을 놓은 위치에 따라 행, 열 정보 리스트에 저장 해당 행, 열엔 퀸 못놓음

def is_possible():
    return is_row and is_column and is_diagonal

def is_row(i):
    if i not in row_list:
        return True

def is_column(j):
    if j not in column_list:
        return True

def is_diagonal(i, j):
    if [i,j] not in diagonal_list:
        return True
    directions = [(1,1),(1,-1),(-1,1),(-1,-1)]
    for direction in directions:

def solution(n):
    board = [[[0] for _ in range(n)] for _ in range(n)]
    row_list = []
    column_list = []
    diagonal_list = []
    def backtrack(start,)
    for i in range(start, n): # 행
        for j in range(n): # 열
            if board[i][j] == 0:
                if is_possible():
                    board[i][j] = 1
                    row_list.append(i)
                    column_list.append(j)

다른 풀이

# ➊ 퀸이 서로 공격할 수 없는 위치에 놓이는 경우의 수를 구하는 함수
def getAns(n, y, width, diagonal1, diagonal2):
  ans = 0
  # ➋ 모든 행에 대해서 퀸의 위치가 결정되었을 경우
  if y == n:
    # ➌ 해결 가능한 경우의 수를 1 증가시킴
    ans += 1
  else:
    # ➍ 현재 행에서 퀸이 놓일 수 있는 모든 위치를 시도
    for i in range(n):
      # ➎ 해당 위치에 이미 퀸이 있는 경우, 대각선 상에 퀸이 있는 경우 스킵
      if width[i] or diagonal1[i + y] or diagonal2[i - y + n]:
        continue
      # ➏ 해당 위치에 퀸을 놓음
      width[i] = diagonal1[i + y] = diagonal2[i - y + n] = True
      # ➐ 다음 행으로 이동하여 재귀적으로 해결 가능한 경우의 수 찾기
      ans += getAns(n, y + 1, width, diagonal1, diagonal2)
      # ➑ 해당 위치에 놓인 퀸을 제거함
      width[i] = diagonal1[i + y] = diagonal2[i - y + n] = False
  return ans

def solution(n):
  # ➒ getAns 함수 호출하여 해결 가능한 경우의 수 찾기
  ans = getAns(n, 0, [False] * n, [False] * (n * 2), [False] * (n * 2))
  return ans

출처 => 코딩테스트 합격하기

풀이 해석

• y가 n까지 가는동안 백트래킹을 하며 진행되므로 y == n이 되었을 경우 ans += 1을 해준다
• 열, 대각선 1,2로 나누어 이를 통해 체스를 둘 수 있는 지 판별
• 둘 수 있을 경우 True로 바꾸어 그다음부터는 놓을 수 없게 변경
• 찾거나 못찾았거나 재귀 나올때마다 width, diagonal1,2 초기화

배울점

• 백트래킹 사고
• 함수를 열, 대각선 1,2를 변수로하여 제작하는 사고
• 변수에 바로 리스트를 적용하여 넣기 => 식 간략화