"농부는 대체되었다" 정렬 알고리즘 구현기
배경: 선인장 시스템
게임 "농부는 대체되었다"에서 선인장(Cactus)은 특별한 수확 시스템을 가지고 있다.
정렬 보상
- 다 자란 선인장이 정렬되어 있으면 이웃도 재귀적으로 수확
- n개 동시 수확 → n² 획득
32x32 맵을 완벽히 정렬하면 1024개가 한 번에 수확되어 1,048,576개를 얻는다. 정렬하지 않으면 1개씩 수확해서 1024개뿐. 정렬의 힘이다.
정렬 조건
선인장이 정렬된 것으로 인정받으려면:
- 북쪽, 동쪽 이웃: 크기가 같거나 큼
- 남쪽, 서쪽 이웃: 크기가 같거나 작음
즉, 좌하단(0,0) → 우상단 방향으로 오름차순 정렬해야 한다.
문제: 게임의 제약사항
일반적인 정렬 알고리즘은 배열의 아무 위치나 접근할 수 있다. 하지만 이 게임에서는:
- 순간이동 불가: 드론은 한 칸씩만 이동
- 인접한 것만 교환:
swap(direction)은 현재 위치와 한 칸 옆만 교환 - 시간 = 비용: 모든 행동(move, swap)이 1틱 소모
퀵소트? 머지소트? 쓸 수 없다. 버블 정렬이 최적해가 되는 희귀한 상황이다.
구현 1: 가로 방향 버블 정렬
def bubble_sort_hor():
for i in range(W):
for j in range(W):
if j < W-1 and measure('East') < measure():
swap('East')
move('East')작동 방식
- 한 줄을 동쪽으로 쭉 이동하면서
- 현재 위치가 동쪽보다 크면 swap
- 끝까지 가면 다시 처음으로 (랩어라운드)
- W번 반복
랩어라운드 활용
게임에서 맵 끝에서 move(East)하면 반대편으로 순간이동한다. 이걸 이용해서 한 방향으로만 계속 이동하면서 정렬할 수 있다.
[3][1][2] → move(East) 계속
↓
[1][2][3] → 정렬 완료구현 2: 세로 방향의 문제
가로는 잘 됐다. 그런데 세로는?
문제: 세로 방향은 랩어라운드가 게임 로직상 다르게 동작하거나, 맵 구조상 활용이 어려웠다.
한 방향으로만 쭉 가는 버블 정렬을 쓸 수 없었다. 그래서 왔다갔다 하는 정렬을 구현했다.
def cocktail_sort_ver():
index = 0
while index < H-1:
index = 0
# 위로 올라가면서 정렬
while position[1] != H-1:
if measure('North') > measure():
swap('North')
else:
index += 1
move('North')
index = 0
# 아래로 내려가면서 정렬
while position[1] != 0:
if measure('North') > measure():
swap('North')
else:
index += 1
move('South')칵테일 정렬 (Cocktail Shaker Sort)
구현하고 나서 알았다. 이게 칵테일 정렬이라는 이름이 있었다!
정의
- 양방향 버블 정렬 (Bidirectional Bubble Sort)
- 셰이커 정렬 (Shaker Sort)
버블 정렬은 한 방향으로만 순회하지만, 칵테일 정렬은 앞→뒤, 뒤→앞을 번갈아 수행한다.
왜 "칵테일"인가?
칵테일 셰이커를 흔들 때 위아래로 왔다갔다 하는 모습에서 유래했다.
버블 정렬 vs 칵테일 정렬
| 구분 | 버블 정렬 | 칵테일 정렬 |
|---|---|---|
| 순회 방향 | 한 방향 | 양방향 |
| 거북이 문제 | 있음 | 완화됨 |
| 구현 복잡도 | 단순 | 약간 복잡 |
| 최선 시간 복잡도 | O(n) | O(n) |
| 평균/최악 시간 복잡도 | O(n²) | O(n²) |
| 공간 복잡도 | O(1) | O(1) |
"거북이 문제"란?
버블 정렬에서 작은 값이 배열 끝에 있으면, 한 번 순회에 한 칸씩만 이동한다. 이걸 "거북이"라고 부른다.
[2, 3, 4, 5, 1] ← 1이 거북이칵테일 정렬은 양방향이라 거북이가 빠르게 제자리를 찾는다.
칵테일 정렬이 더 빠른 경우
거북이가 있을 때 확연한 차이가 난다.
[2, 3, 4, 5, 1]
- 버블 정렬: 4번 순회 필요
- 칵테일 정렬: 2번 순회로 해결더 극단적인 예:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
- 버블 정렬: 10~11번 순회 필요
- 칵테일 정렬: 3번 순회로 해결일반적으로 칵테일 정렬은 버블 정렬보다 최대 2배 빠르다.
둘 다 비슷한 경우 (반례)
이미 정렬된 배열 또는 역순 정렬된 배열에서는 큰 차이가 없다.
[5, 4, 3, 2, 1] ← 완전 역순
- 버블 정렬: O(n²)
- 칵테일 정렬: O(n²) (똑같이 느림)역순 배열은 거북이가 없고 모든 요소가 이동해야 해서, 양방향의 이점이 없다.
[1, 2, 3, 4, 5] ← 이미 정렬됨
- 버블 정렬: O(n) - 한 번 순회로 확인
- 칵테일 정렬: O(n) - 똑같이 빠름결론
칵테일 정렬은 버블 정렬의 개선판이지만, 극적인 성능 향상은 아니다. 실무에서는 퀵소트, 머지소트, 팀소트 등을 사용한다. 하지만 이 게임처럼 특수한 제약 조건에서는 여전히 유효한 선택이다.
실제 게임에서의 적용
맵 구조 (8x8 예시):
[0,0] → → → [7,0]
↑ ↑
↑ ↑
[0,7] → → → [7,7]
정렬 목표: 좌하단(작은 값) → 우상단(큰 값)정렬 순서
- 가로 정렬: 각 행을 bubble_sort_hor()로 정렬
- 세로 정렬: 각 열을 cocktail_sort_ver()로 정렬
이렇게 하면 2D 배열 전체가 정렬되어 최대 수확량을 얻을 수 있다.
배운 점
- 제약이 알고리즘을 결정한다: 순간이동이 안 되니까 버블 정렬이 최선
- 고전 알고리즘의 가치: 현대에는 잘 안 쓰이는 O(n²) 정렬도 상황에 따라 최적해
- 바퀴의 재발명: 칵테일 정렬이라는 기존 알고리즘을 모르고 직접 구현했다. 구현하고 나서야 이름을 알게 됨
- 게임으로 배우는 CS: 정렬 알고리즘을 게임 퍼즐로 자연스럽게 학습
참고 자료
