[백준-9663] N-Queen 파이썬, 백트랙킹, 파이썬 전역변수, enumerate

# 문제

 

# 풀이

 백트래킹기법을 사용하여 문제를 풀었다. 기존 탐색이나 반복문으로 풀게 되면 중간에 퀸을 놓을 수 없는 경우에도 그 다음에 대한 탐색을 실시할 것이다. 그렇기 때문에 중간에 이미 틀린 길이라면 이 후 반복을 중지하고 그 뒤로 돌아가야한다. 그렇게 하기 위해 백트래킹 기법을 사용해서 문제를 풀었다.

 첫 행의 열들은 각각의 시작점이 된다. 그 기점으로 시작해서 가지가 뻗어나가기 때문에 시작위치를 지정해주었다. 이후 dfs를 이용해서 재귀함수로 다시 호출해나가는 방법으로 문제를 풀었다. 

  for candidate_col in range(N):
    if is_available(cur_row, candidate_col, upper_queen_info):
      upper_queen_info.append(candidate_col)
      back_tracking(N, upper_queen_info, result)
      upper_queen_info.pop()

위와같이 append후에 back_tracking()함수를 재귀적으로 호출하고 바로 pop()을 하는 모습이 코드를 짜면서 계속해서 헷갈렸다. 그러나 back_tracking()함수의 종료조건을 작성할때 즉, dfs가 맨 마지막 행까지의 수행이 끝나면 들어가게 되는 곳에서 최종 result의 정보를 저장해두기에 저 곧 까지만 가면 끝이다. 저 지점에 도달하지 못하고 dfs가 return되면 실패한 것이기 때문에 dfs이후 pop을 호출해서 현재 넣었던 후보군에서 다시 제거하도록 작성했다. 

## 시간초과

 is_availabe을 확인하면서 수직검사와 대각검사를 각각 실시했었는데 반복문이 한 반복문에서 해결 할 수 있도록 했다. 왜냐하면 코드를 제출하고 시간초과가 났기 때문이다..

 그렇게 하고도 시간초과가 pypy3로 제출하니까 맞았다. 백트레킹을 파이썬으로 풀때는 시간초과를 해결하는 것이 관건이라고 한다. 아직 알고리즘 공부를 시작한지 얼마 안됐고, 처음 써보는 것이기 때문에 다음번에는 파이썬으로 완벽히 해결 해 보고 싶다. 

 추가적으로 back_tracking이 실행될때 n이 4라면 5번째에서 return되는데 이부분을 한단계라도 줄이면 가능성이 있지 않을까 조심스레 추측해본다.

 

## 파이썬 

 

### enumerate

js나 코틀린에서 사용했던거 forEach와 같이 index,value로 리스트에 접근이 가능한 줄 알았지만, enumerate를 사용해야 했다.

# 틀린코드
for queen_row, queen_col in info:
  if col == queen_col or abs(col - queen_col) == abs(row-queen_row):
    return False

# 맞는 코드
for queen_row, queen_col in enumerate(info):
  if col == queen_col or abs(col - queen_col) == abs(row-queen_row):
    return False

 

### global

파이썬에서 전역변수를 사용하기 위해서는 전역위치에 cnt를 선언 하고 global이라는 키워드를 사용해야 한다.

# 전역 
cnt = 0

# 올바른 사용법
def foo():
	global cnt
    cnt +=1

# 틀린 사용법
def foo():
	global cnt += 1

 

# 코드

'''
  수직체크, 수평체크, 대각선 체크가 필요
  백트레킹기법을 사용해서, 조건에 맞지 않으면 그 뒤는 탐색할 필요가 없음
'''
import sys

cnt = 0

def is_available(row, col, info):
  # 들어온 row와 col에 대한 수직검사, 수평검사

  # 수직검사
  # for i in info:
  #   if col == i:
  #     return False

  # 대각 검사 + 대각검사
  for queen_row, queen_col in enumerate(info):
    if col == queen_col or abs(col - queen_col) == abs(row-queen_row):
      return False

  return True


def back_tracking(N, upper_queen_info, result):
  cur_row = len(upper_queen_info)

  # 재귀 함수 종료조건 작성
  if cur_row == N:
    result.append(upper_queen_info[:])
    global cnt
    cnt +=1
    return

  for candidate_col in range(N):
    if is_available(cur_row, candidate_col, upper_queen_info):
      upper_queen_info.append(candidate_col)
      back_tracking(N, upper_queen_info, result)
      upper_queen_info.pop()

  return


def answer(N):
  result = []
  for first_col in range(N):
    list_strat = [first_col]
    back_tracking(N, list_strat, result)
  return result


if __name__ == '__main__':
  N = int(sys.stdin.readline().strip())
  a = answer(N)
  # print(a)
  print(cnt)

 

# 풀면서