1. 서론
사다리타기(Amida Lotto)는 인접한 세로선 사이에 가로선을 추가하여 사람들의 위치를 뒤섞는 게임이다.
주어진 가로선 집합 중 일부만 선택하여도 전체 가로선을 모두 사용했을 때와 동일한 결과가 나오는 최소 조합을 찾는 문제를 다룬다.
초기 구현은 실제 이동 경로를 삼중 루프 시뮬레이션으로 계산했으나, 본질을 분석하여 swap 연산 기반으로 리팩터링했다.
2. 문제 정의
- 입력
- 세로선 개수
n
- 가로선 후보 개수
m
- 각 가로선:
(left, row) → left – 연결되는 왼쪽 세로선 번호, row – 위에서부터 가로선의 순서
- 출력
- 평가 지표
3. 초기 구현 – 이동 기반 시뮬레이션
3.1 핵심 코드
public static String simulation(List<Line> linesForSimulation) {
if (linesForSimulation.isEmpty()) {
return Arrays.toString(IntStream.rangeClosed(1, n).toArray());
}
int[] people = new int[n];
linesForSimulation.sort(Comparator.comparingInt(line -> line.row));
int maxRow = linesForSimulation.get(linesForSimulation.size() - 1).row;
for (int i = 1; i <= n; i++) {
int col = i;
for (int row = 0; row <= maxRow; row++) {
for (Line line : linesForSimulation) {
if (line.row != row) continue;
if (line.left == col) { col++; break; }
else if (line.right == col) { col--; break; }
}
}
people[col - 1] = i;
}
return Arrays.toString(people);
}
3.2 복잡도
- 시뮬레이션 1회:
O(n · m²)
n – 사람 수, 최악의 경우 각 row마다 m선을 선형 검색
- 전체 탐색: 백트래킹 분기
2^m → O(n · m² · 2^m)
3.3 장단점
| 장점 | 단점 |
|---|
| 직관적, 디버깅·시각화 용이 | 중첩 루프가 많아 매우 느림 |
4. 사다리타기의 본질 – “가로선 = Swap”
가로선은 왼쪽 세로선에서 내려오던 사람과 오른쪽 세로선에서 내려오던 사람의 위치를 교환한다.
즉, 가로선의 효과는 순수한 swap(arr[left-1], arr[left]) 로 표현할 수 있다.
4.1 동치성 증명 요약
- 모든 세로선은 위→아래 단방향이며 교차하지 않는다.
- 사람이
row 층에서 좌우 이동하면, 그 이후 경로는 새 위치에서 그대로 이어진다.
- 두 사람이 교차된 이후 다시 만날 수 없으므로, 최종 결과는 swap 연산들의 순차적 적용으로 완전히 결정된다.
5. 개선 구현 – swap 기반 시뮬레이션
5.1 핵심 코드
public static String simulation(List<Line> linesForSimulation) {
if (linesForSimulation.isEmpty()) {
return Arrays.toString(IntStream.rangeClosed(1, n).toArray());
}
int[] people = IntStream.rangeClosed(1, n).toArray();
for (Line line : linesForSimulation) {
int l = line.left - 1;
int r = line.right - 1;
int tmp = people[l];
people[l] = people[r];
people[r] = tmp;
}
return Arrays.toString(people);
}
5.2 복잡도
- 시뮬레이션 1회:
O(n) 이 아닌 O(m)
- 전체 탐색:
O((n + m) · 2^m)
5.3 장단점
| 장점 | 단점 |
|---|
| 실행 시간 대폭 감소, 구현 간결 | 가로선이 인접 세로선만 연결된다는 전제 필요 |
6. 코드‑레벨 차이점 요약
| 구분 | 이동 시뮬레이션 | swap 시뮬레이션 |
|---|
| 결과 계산 | col · row 삼중 루프 | 가로선 순회하며 swap |
| 리프 한 번 비용 | O(n · m²) | O(m) |
| 복잡도(전체) | O(n · m² · 2^m) | O((n+m) · 2^m) |
| 메모리 | O(n) | O(n)(동일) |
| 가독성 | 경로 추적 코드 장황 | 배열 swap 코드 간결 |
7. 성능 비교 실험
| n | m | 이동 기반 실행(ms) | swap 기반 실행(ms) |
|---|
| 10 | 10 | 45 | 3 |
| 50 | 10 | 230 | 10 |
| 50 | 15 | 820 | 37 |
단일 스레드, JDK 21, Mac M2 – Release 모드.
swap 방식이 최대 20배 이상 빠름.
8. 가독성과 유지보수 평가
- 추상화 수준
- 이동 방식은 “어떻게 움직이나”에 초점 → 로직 장황
- swap 방식은 “무엇이 바뀌나”만 표현 → 선언적
- 디버깅
- 이동 방식은 좌표 추적이 쉬워 시각화에 장점
- swap 방식은 단순 상태 배열만 보면 됨
- 확장성
- 가로선이 인접 세로선만 연결된다는 규칙이 유지되는 한 swap 방식이 압도적으로 우수
- 규칙이 깨지면(비인접 연결 허용 등) 이동 방식 재도입 필요
9. 결론
- 사다리 가로선은 순수 swap 연산으로 추상화할 수 있다.
- 이동‑기반 시뮬레이션을 swap‑기반으로 전환하면
- 시뮬레이션 비용
O(n · m²) → O(m)
- 전체 탐색 비용
O(n · m² · 2^m) → O((n+m) · 2^m)
- 실측 성능 최대 20배 개선
- 알고리즘 구현에서 “동작을 직접 흉내 내지 않고, 본질적 상태 변화만 모델링”하면
- 코드가 짧아지고
- 실행이 빨라지며
- 이해·유지보수가 쉬워진다.
