🤍
백트래킹
: 필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법.
N-Queens 문제
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively. ( 51. N-Queens🔗 )
def nqueen(n):
"""
visited 의 인덱스는 행, 값은 열을 나타낸다.
(1, 3)에 놓은 경우, visited[1] = 3 으로 표현됨. (1차원 배열로 2차원 좌표값을 나타냄)
예시) n=4 이고 visited = [1, 3, 0, 2] 인 경우,
체스판을 그려보면 아래와 같다. (1이 퀸)
0 1 0 0 (0,1)
0 0 0 1 (1,3)
1 0 0 0 (2,0)
0 0 1 0 (3,2)
"""
visited = [-1] * n # -1 = 두지 않음
cnt = 0 # 경우의 수
answers = []
def is_ok_on(nth_row): # 백트래킹
"""
n번째(nth) 행에 퀸을 놓았을 때, 올바른 수인지 검사한다.
nth 행의 퀸 위치와, 0번째 행부터 n-1번째 행까지 놓여진 퀸의 위치를 비교한다.
nth 행에 놓여진 퀸이 규칙을 깼다면 False 를 반환한다.
"""
# 0번째 행 ~ nth_row-1번째 행의 퀸 위치를 차례대로 꺼내온다.
for row in range(nth_row):
# 방금 놓여진 nth 퀸은 (nth_row, visited[nth_row]) 에 놓여져있다.
# 각 행에 차례대로 단 한 번만 두기 때문에 행이 겹치는 것은 검사하지 않아도 된다.
# 1) 열 번호가 겹치지는 않는지? visited[nth_row] == visited[row]:
# 2) 또는 대각선으로 존재하지는 않는지? nth_row - row == abs(visited[nth_row] - visited[row]) 살펴본다.
if visited[nth_row] == visited[row] or nth_row - row == abs(visited[nth_row] - visited[row]):
return False
return True
def dfs(row):
"""
row 는 퀸을 놓을 행번호를 의미한다.
dfs(0) 은 0번째 행에서 퀸의 위치를 고르는 것이고,
dfs(1) 은 1번째 행에서 퀸의 위치를 고르는 것이고,
...
dfs(n-1) 은 n-1번째 행에서 퀸의 위치를 고르는 것이다.
따라서 row 는 n-1까지 가능하며, n이 되었다는 것은 n개의 퀸을 모두 올바른 위치에 두었다는 의미이다.
"""
# 0 ~ n-1 행에 퀸을 모두 하나씩 두었을 때 경우의 수를 1 증가시키고 재귀탐색을 종료한다.
if row >= n:
# nonlocal 은 지역변수가 아님을 의미한다.
nonlocal cnt
cnt += 1
print("*" * 80)
print(f"{cnt}번째 답 - visited: {visited}")
grid = [['.'] * n for _ in range(n)]
for idx, value in enumerate(visited):
grid[idx][value] = 'Q'
result = []
for row in grid:
print(row)
result.append(''.join(row))
answers.append(result)
################
return
# visited[row] 의 값을 결정한다.
# n*n 의 체스판이므로 가능한 열의 범위는 0 ~ n-1 이다.
for col in range(n):
# (row, col) 위치에 퀸을 두었다고 가정하고, 규칙을 깨지 않는다면 row+1 행에 다시 퀸을 둔다.
visited[row] = col
if is_ok_on(row):
dfs(row + 1)
# 0번째 행에 퀸을 둔다.
dfs(0)
return answers
assert nqueen(4) == [[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]]
ALGORITHM CODE KATA
Ⅰ. 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요. (school.programmers.co.kr)
def solution(n, lost, reserve): # 전체 학생 수, 도난당한 학생들의 번호, 여벌 있는 학생들 번호
# 도난당한 학생이 여벌 체육복을 가지고 있었던 경우 처리(빌리지도 빌려주지도 않는 인원).
lost = set(lost)
reserve = set(reserve)
common = lost & reserve
lost -= common
reserve -= common
answer = n - len(lost) # 체육복을 입을 수 있는 학생인원 최댓값.
# 10, [1, 2, 3, 4, 5, 6], [1, 2, 3] >>> 7 의 반례 처리를 위해 common 원소를 lost와 reserve에서 제거한 후 answer 정의.
for i in sorted(lost):
if i - 1 in reserve:
answer += 1
reserve.remove(i - 1)
elif i + 1 in reserve:
answer += 1
reserve.remove(i + 1)
return answer