Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 코딩테스트준비
- 자바
- sort
- python
- 탐욕알고리즘
- 파이썬
- API
- 장고
- SQL
- github
- 코딩테스트
- greedy
- java
- 알고리즘
- 리그오브레전드
- Django
- 롤
- lol
- drf
- 프로그래머스
- 백준
- programmers
- 그리디알고리즘
- 스파르타내일배움캠프
- 그리디
- 스파르타내일배움캠프TIL
- 내일배움캠프
- git
- 라이엇
- Riot
Archives
- Today
- Total
Lina's Toolbox
[자료구조] 백트래킹, N-Queen 문제 풀기 본문
스파르타 내일 배움 캠프 AI 웹개발 과정/algorithm & data structure
[자료구조] 백트래킹, N-Queen 문제 풀기
Woolina 2024. 7. 18. 18:00DFS, BFS 관련 내용은 이전 포스팅 참조
https://kimwoolina.tistory.com/33
백트래킹
필요없는 경우를 가지치기(pruning)함으로써 시간복잡도를 줄이는 방법
DFS, BFS와 같은 완전탐색 기법들을 더 효율적으로 할 수 있게 만들어주는 기법!
사실 모든 문제에서 완전 탐색을 하는 것은 쉽지 않다. ➡️ 필요한 경우의 수만 확인하는 백트래킹 사용
N-Queen 문제
https://leetcode.com/problems/n-queens/description/
- N*N 체스판에 N개의 퀸을 배치할 수 있는 경우의 수를 센다.
- 퀸은 상하좌우, 대각선 방향으로 거리 제한 없이 이동할 수 있다
- (퀸은 겹친다면 잡아먹을 수 있다.)
- N=8인 경우, 경우의 수는 다음과 같다.
- 64 * 63 * ... * 57 = 178,462,987,637,760
- C 기준 1초에 1억 번을 연산하므로 모든 경우의 수를 탐색하는데 약 20.6시간이 소요된다.
- ➡️ 모든 경우의 수를 탐색하는 것은 사실상 불가능.
- ➡️ 백트래킹 기법 사용!
def nqueen(n):
"""
visited 의 인덱스는 행, 값은 열을 나타낸다.
퀸을 (1, 3)에 놓은 경우, visited[1] = 3 으로 표현하겠다는 것.
(어차피 퀸들을 같은 행, 열에 둘 수 없으므로 이렇게 1차원 배열로도 표현할 수 있다.)
예시) n=4 이고 visited = [1, 3, 0, 2] 인 경우,
체스판을 그려보면 아래와 같다. (1이 퀸)
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
"""
visited = [-1] * n
cnt = 0 # 퀸 배치 경우의 수 # 출력 시 사용
answers = []
# 이 row가 퀸을 둘 수 있는 장소인지 확인
# 백트래킹의 핵심 부분인 코드
def is_ok_on(nth_row):
"""
n번째(nth) 행에 퀸을 놓았을 때, 올바른 수인지 검사한다.
nth 행의 퀸 위치와, 0번째 행부터 n-1번째 행까지 놓여진 퀸의 위치를 비교한다.
nth 행에 놓여진 퀸이 규칙을 깼다면 False 를 반환한다.
"""
# 0번째 행 ~ nth_row-1번째 행의 퀸 위치를 차례대로 꺼내온다.
# 영상에서 n-1이라고 말하는데 오류입니다. 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]) 살펴본다.
# nth_row - row == abs(visited[nth_row] - visited[row]) ➡️ x좌표의 차이 == y값의 좌표의 차이
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}")
# 모든 요소가 '.' 인 n길이의 리스트 만듦
grid = [['.'] * n for _ in range(n)]
# 퀸이 있는 자리에 Q넣어줌
for idx, value in enumerate(visited):
grid[idx][value] = 'Q'
result = []
for row in grid:
print(row)
# 마지막에 한꺼번에 출력하기 위한 과정
# ['.', 'Q', '.', '.'] => '.Q..'
result.append(''.join(row))
# answer: 가장 마지막 출력이 될 부분
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
2차원 배열로 하지 않고 1차원배열로 표현하면 시간복잡도가 N**2에서 N으로 줄 수 있어서
훨씬 시간 복잡도가 좋아진다!
nqueen(4)의 실행결과
휴 n_queen 문제 코드 겨우 다 이해했다..
'스파르타 내일 배움 캠프 AI 웹개발 과정 > algorithm & data structure' 카테고리의 다른 글
[알고리즘] 정렬 - 버블정렬, 선택정렬, 삽입정렬, 퀵소트(퀵정렬) , 배열정렬, 병합정렬, 힙정렬 (2) | 2024.07.22 |
---|---|
[자료구조] 완전 이진 트리, 이진 트리의 최대 깊이, 이진 탐색 트리 (0) | 2024.07.19 |
[자료구조] 트리, DFS(깊이우선탐색), BFS(넓이우선탐색) (4) | 2024.07.16 |
[자료구조] 연결리스트 (링크드 리스트), array vs linked list (0) | 2024.07.13 |
[자료구조] 힙(Heap), 최대힙(MaxHeap), 최대힙 삽입, 최대힙 추출, 이진트리, 이진탐색트리 (0) | 2024.07.12 |