🚶‍♂️Road to 코테(11) - 백트래킹

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
즉, 현재 상태에서 가능한 모든 선택지를 다 플레이해보는 방법이 백트래킹이다.
-> 상태공간트리라고도 한다.

현재 상태에서 가능한 모든 경우의 수를 생각해보며 결과까지 생각해본다.
오목이라고 하면 어떠한 한 수를 둘 때 상대가 놓을 수, 나의 다음 수를 생각하는 것.

DFS와 혼동할 수 있지만 백트래킹은 불필요한 탐색을 하지 않는다.
예를 들어, 132,234,123 중 123을 찾을때 132에 접근했을때 10의 자리수가 다르기 때문에 다음 수로 바로 넘어간다.

재귀의 성격을 띄고 있다.

백트래킹 코드는 아래와 같이 할 수 있다.

def backtrack(candidate):
	# 만약 현재 후보군이 유효한 해라면 정답 처리하고 backtrack 함수를 종료
    if find_solution(candidate):
        output(candidate)
        return
    
    # 반복문을 돌면서 가능한 모든 후보군에 대해 탐색
    for next_candidate in list_of_candidates:
    	# 유효한 후보군인 경우에만 탐색 진행
        if is_valid(next_candidate):
            # 이 후보군을 우선 추가하고,
            place(next_candidate)
            # 후보군을 추가한 상태에서 다음 후보군에 대해서 탐색 진행
            backtrack(next_candidate)
            # 해당 후보군에 대한 탐색을 종료한 이후에는 제거
            remove(next_candidate)

연습문제1 - 15649 N과 M(1)

import sys

n,m=map(int,sys.stdin.readline().split())
ans=[]

def back():
  if len(ans)==m: #base condition
    print(" ".join(map(str,ans))) #m개를 모두 선택했으면 출력하고
    return #현재 재귀 함수 종료한다. 
  for i in range(1,n+1): #재귀 함수
    if i not in ans: #i가 정답 리스트에없으면
      ans.append(i) # 리스트에 추가
      back() 
      ans.pop() #return을 하면 다시 여기로 돌아옴. 

back()

연습문제2 - 9663 N-Queen

import sys
input=sys.stdin.readline
n=int(input())
sys.setrecursionlimit(10 ** 4)

"""
queen은 상하좌우대각선 모두 공격가능
같은 열 불가, 같은 행 불가
대각선 불가
[행 index+1,열 index+1],[행 index-1,열 index-1] 불가
[행 index-1,열 index+1],[행 index+1,열 index-1] 불가
현재 행이 보드판 사이즈(n)보다 크면 가능한 방법 한 가지 찾았다 생각해 1을 리턴.
현재 칸의 열, 대각선, reverse대각선(오른쪽 위로)에 퀸이 놓아져 있으면 다음 열로 넘어간다.
현재 칸에 퀸을 놓을 수 있으면 row,col을 계산해서 열,대각선,reverse대각선에 넣는다


"""
cnt=0

def chess(row,cross,cross_reverse,cols):
  global n
  if row==n:
    
    return 1
  
  sol = 0
  for col in range(n):
    curr_cross= row-col #현재 기준 Right to left 아래 대각선은 행-열
    curr_cross_reverse=row+col #현재 기준  Left to right 대각선은 열과 행 더하기
    
    
    if (col in cols or curr_cross in cross or curr_cross_reverse in cross_reverse):
      continue
    
    cols.add(col)
    cross.add(curr_cross)
    cross_reverse.add(curr_cross_reverse)
    sol+=chess(row+1,cross,cross_reverse,cols)
    
    #만약에 return이 나오면 되돌아가면서 set에서 추가했던 요소를 삭제한다..
    cols.remove(col)
    cross.remove(curr_cross)
    cross_reverse.remove(curr_cross_reverse)
  
  return sol

print(chess(0,set(),set(),set()))

왜 시간초과가 나올까 pypy3를 사용하니 해결
🚩PyPy3 : JIT(Just In Time) 컴파일을 사용하여 느린 실행속도를 개선한다.
Python3가 메모리, 속도 측에서 우세하고, 반복을 사용하는 경우 PyPy3가 우세하다.

연습문제3 - 15650 N과 M(2)

import sys

n,m=map(int,sys.stdin.readline().split())
ans=[]

def back():
  if len(ans)==m: #base condition
    print(" ".join(map(str,ans))) #m개를 모두 선택했으면 출력하고
    return #현재 재귀 함수 종료한다. 
  for i in range(1,n+1): #재귀 함수
    if i not in ans: #i가 정답 리스트에없으면
      ans.append(i) # 리스트에 추가
      back() 
      ans.pop() #return을 하면 다시 여기로 돌아옴. 

back()