시뮬레이션(Simulation) 알고리즘은 문제에서 주어진 조건을 코드로 그대로 구현하며 상태를 변화시키는 방식으로 문제를 해결하는 알고리즘이다. 말 그대로 “문제의 상황을 그대로 재현해보는 전략”이다.
즉, 상황을 한 단계씩 따라가면서 시뮬레이션처럼 구현하고 그 과정에서 어떤 값이 변화하는지를 추적해가며 정답을 도출한다. 특정한 자료구조나 고급 알고리즘보다 문제 해석력과 구현력이 중요한 유형이다. 조건이 복잡하거나 규칙이 다양한 문제에서 자주 등장하며 특히 2차원 배열, 게임판, 로봇 이동, 물체 시뮬레이션 등에서 자주 쓰인다.
장점
- 문제만 제대로 이해하면 설계가 단순함
- 다양한 알고리즘 기법과 결합 가능 (BFS, DFS, 큐 등)
- 제한된 범위에서는 완전 탐색이 가능해 정확한 정답 도출
단점
- 구현량이 많고 디버깅이 어려움
- 작은 조건 하나 누락 시 오답 발생
- 대개
O(N^2)~O(N^3)으로 시간 초과 주의 필요
대표 문제
| 문제 유형 | 문제 설명 | 핵심 전략 | 예시 |
|---|---|---|---|
| 로봇 청소기 | 지정된 규칙에 따라 로봇 이동 및 청소 | 방향 전환, 상태 체크, 백트래킹 필요 | 백준 14503 |
| 게임판 시뮬레이션 | 블록 이동, 터트리기, 중력 등 게임 구현 | 반복 조건, 맵 갱신, 상태 변화 추적 | 프렌즈4블록, 테트리스 등 |
| 톱니바퀴 회전 | 서로 영향을 주는 객체들 간의 회전 시뮬레이션 | 인접 조건 판별, 상태 전이 구현 | 백준 14891 |
| 구슬 탈출 | 두 개의 구슬을 동시에 굴려서 탈출 조건 확인 | BFS + 방향별 반복 시뮬레이션 | 백준 13459 |
| 캐릭터 이동 | 명령어에 따라 좌표 이동 및 맵 탐색 | dx/dy 배열 활용, 범위 체크 | 삼성 SW 역량 테스트 기출 |
| 스프레드 시뮬레이션 | 바이러스, 불, 물 등이 확산되는 과정을 재현 | 큐 + BFS or 단계별 업데이트 | 불!, 바이러스 퍼지기 문제 등 |
적용 조건
시뮬레이션 알고리즘은 문제에 특별한 수학적 최적화가 없고 그저 조건을 순서대로 따라가면 정답을 찾을 수 있는 구조에서 사용된다. 아래 조건을 만족하는 문제일수록 시뮬레이션으로 풀기 적합하다.
1. 상태의 변화가 명확하게 정의되어 있다.
예: 좌표 이동, 값 증가/감소, 방향 회전, 스위치 On/Off 등
2. 하나씩 단계를 밟아가며 처리해야 한다.
예: 순서에 따라 변화가 누적되거나 이전 상태에 영향을 받는 구조
3. 복잡한 알고리즘보다 구현 중심의 로직이 중요하다.
예: 조건 분기, 반복 처리, 순서가 중요한 흐름
대표 예제
1. 캐릭터 이동 시뮬레이션
문제: N x N 격자에서 캐릭터가 "상하좌우" 명령에 따라 이동하며 최종 위치 출력
조건
- 시작 좌표:
(0, 0) - 명령어:
"R", "R", "R", "U", "D", "D" - 범위를 벗어나면 무시
public class CharacterMovementSimulation {
public static void main(String[] args) {
int n = 5;
int x = 0, y = 0;
String[] moves = {"R", "R", "R", "U", "D", "D"};
// 방향: R, L, U, D 순서
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
String[] directions = {"R", "L", "U", "D"};
for (String move : moves) {
for (int i = 0; i < 4; i++) {
if (move.equals(directions[i])) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
x = nx;
y = ny;
}
break;
}
}
}
System.out.println("최종 위치: (" + x + ", " + y + ")");
}
}실행 과정
- R →
(0,1)→ R →(0,2)→ R →(0,3) - U →
(-1,3)→ 범위 밖 → 무시 - D →
(1,3)→ D →(2,3)
최종 위치는 (2,3)이다.
2. 로봇 청소기 시뮬레이션
문제: 로봇이 현재 방향 기준으로 좌우회전하며 빈 칸을 청소하는 문제
조건
- 네 방향 탐색
- 후진 조건, 회전 조건
- 벽에 닿으면 종료
class RobotCleaner {
static int[][] map;
static boolean[][] cleaned;
static int n, m;
static int[] dx = {-1, 0, 1, 0}; // 북동남서
static int[] dy = {0, 1, 0, -1};
static void clean(int x, int y, int dir) {
if (!cleaned[x][y]) {
cleaned[x][y] = true;
}
for (int i = 0; i < 4; i++) {
dir = (dir + 3) % 4; // 왼쪽 회전
int nx = x + dx[dir];
int ny = y + dy[dir];
if (map[nx][ny] == 0 && !cleaned[nx][ny]) {
clean(nx, ny, dir);
return;
}
}
int back = (dir + 2) % 4;
int bx = x + dx[back];
int by = y + dy[back];
if (map[bx][by] == 0) {
clean(bx, by, dir);
}
}
}📝 느낀점
시뮬레이션 알고리즘은 다른 알고리즘처럼 정형화된 풀이 방식이 있는 게 아니라 문제에 주어진 조건을 얼마나 정확하게 구현하느냐가 핵심이다. 그래서 알고리즘보다는 구현력, 특히 꼼꼼함과 디버깅 능력이 중요하다. 실제로 문제를 풀다 보면 로직 자체는 단순하지만 조건 분기나 상태 갱신에서 실수가 잦고 이게 곧 오답으로 이어지기 때문에 작은 실수 하나가 치명적일 수 있다.
특히 배열 범위 체크나 방향 전환처럼 자주 반복되는 로직일수록 실수를 더 많이 하게 되는데 이를 줄이기 위해선 dx/dy 배열을 북동남서 기준으로 정형화해두고 방향 전환도 (dir + 3) % 4처럼 일정한 규칙을 습관처럼 적용하는 게 도움이 됐다. 단순 구현이라고 가볍게 생각하고 설계 없이 바로 코드를 짜다 보면 중복된 로직이 생기거나 디버깅이 어려워지는 경우가 많았다. 그래서 최근에는 시뮬레이션 문제를 만나면 먼저 현재 상태와 변화 조건, 종료 조건을 나열해보고 간단한 의사코드나 플로우를 먼저 정리하고 구현에 들어가려고 한다.
또한 시뮬레이션 문제는 시간 복잡도를 간과하기 쉬운데 이중 반복문이나 매 연산마다 전체 배열을 순회하는 경우가 많다 보니 입력 범위가 커지면 금방 O(N^3)을 초과하게 된다. 이런 경우엔 매번 맵 전체를 복사하기보단 필요한 상태만 따로 저장하거나 조건을 한 번만 만족하면 루프를 탈출하는 방식으로 반복 횟수를 줄이는 게 중요하다. 이걸 고려하지 않으면 구현은 맞았더라도 시간 초과로 실패하는 경우가 생긴다.
마지막으로 시뮬레이션 문제는 디버깅이 매우 중요하다. 중간에 상태가 어떻게 바뀌는지 직접 출력해보지 않으면 어떤 조건에서 문제가 생겼는지 찾기 어렵기 때문이다. 그래서 구현이 길어질수록 중간 로그 출력이나 맵 상태 출력 코드를 습관처럼 넣어두는 게 실수 파악에 큰 도움이 됐다.
결국 시뮬레이션은 알고리즘 지식보다는 문제를 읽고 흐름을 이해하고 그것을 정확하게 재현해내는 구현 능력을 평가하는 유형이라는 걸 다시 느꼈다. 단순하지만 어렵고 정답보다 디버깅이 더 오래 걸리는 경우가 많아서 문제를 구조적으로 바라보고 설계부터 깔끔하게 잡는 연습이 중요하다는 걸 배웠다.
