시뮬레이션 (Simulation)

정의

시뮬레이션 (Simulation) 은 문제에서 제시한 규칙을 그대로 코드로 옮겨 한 단계씩 따라가는 알고리즘. 복잡한 로직보다 정확한 구현과 엣지 케이스 처리 가 핵심.

PS 에서 “~과정을 T 초 동안 반복한다”, “주어진 명령을 순서대로 실행한다” 같은 표현이 나오면 시뮬레이션.

문제 상황과 동기

보드 게임, 로봇 이동, 큐 처리, 달력, 시계 문제 등에서 과정 자체 를 모델링.

• naive: 규칙을 자연어로 이해만 하고 코드로 안 옮김 → WA.
• simulation (올바른 접근): 문제 조건을 하나하나 if-else / for / while 로 번역. 테스트 케이스 손으로 따라가며 검증.

핵심 통찰: 문제가 묻는 대로 정확히 구현하면 정답. 알고리즘 최적화보다 버그 없는 코드 작성이 목표.

실전에서 “구현”, “시뮬레이션” 은 거의 동의어. 둘 다 문제 조건 1:1 대응.

시각화

핵심 아이디어

문제 지문의 절차 를 그대로 루프 / 조건문으로.

state = initial_state
for t = 1 to T:
    state = apply_rule(state, t)
return state

invariant: 각 시점의 상태가 규칙에 부합. 중간 결과 출력 문제는 각 단계마다 검증.

대표 패턴:

• 시간 진행 (time evolution): for t in 1..T.
• 명령 처리 (command execution): 입력 명령을 큐나 배열로 받아 순차 실행.
• 보드 조작 (grid manipulation): 2D 배열 + 방향 벡터 dx, dy.
• 객체 이동 (object movement): 위치, 방향, 속도 추적.
• 상태 전이 (state machine): 현재 상태 + 입력 → 다음 상태.

알고리즘

단순 시뮬레이션 (보드 게임)

grid = initial_grid
for command in commands:
    if command == "U":
        move_up(grid)
    elif command == "D":
        move_down(grid)
    ...
    print(grid)

큐 처리

queue = [1, 2, 3, ...]
time = 0
while queue is not empty:
    task = queue.pop_front()
    time += task.duration
    process(task)

구현

// 로봇이 N×N 보드를 상하좌우 이동. 명령 실행 후 위치 출력
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, x = 0, y = 0;
  string commands;
  cin >> n >> commands;
  map<char, pair<int,int>> dir = {
      {'U', {-1, 0}}, {'D', {1, 0}},
      {'L', {0, -1}}, {'R', {0, 1}}
  };
  for (char c : commands) {
      int nx = x + dir[c].first;
      int ny = y + dir[c].second;
      if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
          x = nx; y = ny;
      }
  }
  cout << x << " " << y << "\n";
}

# 로봇 이동 시뮬레이션
n = int(input())
commands = input().strip()
x, y = 0, 0
direction = {
  'U': (-1, 0), 'D': (1, 0),
  'L': (0, -1), 'R': (0, 1)
}
for c in commands:
  dx, dy = direction[c]
  nx, ny = x + dx, y + dy
  if 0 <= nx < n and 0 <= ny < n:
      x, y = nx, ny
print(x, y)

// 로봇 이동
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      String commands = sc.next();
      int x = 0, y = 0;
      for (char c : commands.toCharArray()) {
          int nx = x, ny = y;
          if (c == 'U') nx--;
          else if (c == 'D') nx++;
          else if (c == 'L') ny--;
          else if (c == 'R') ny++;
          if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
              x = nx; y = ny;
          }
      }
      System.out.println(x + " " + y);
  }
}

5
RRDD

2 2

3
UUURRRDDD

2 2

복잡도

T = 시뮬레이션 단계 수, S = 한 단계 처리 비용. 보드 전체 순회면 S=O(N^2), 단순 이동이면 S=O(1).

실전 팁

1. 방향 벡터 (dx, dy)

int dx[4] = {-1, 1, 0, 0};   // 상하좌우
int dy[4] = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (in_range(nx, ny)) { /* ... */ }
}

8방향이면 배열 크기 8.

2. 상태 복사 vs 인플레이스 갱신

격자가 동시 갱신이면 next_grid = copy(grid) 필요. 순차 갱신이면 인플레이스.

3. 디버그 출력

각 단계 후 print(state) 추가. 손 계산과 비교.

4. 테스트 케이스 자체 작성

문제 예제만으로 부족할 때, 극단 케이스 (빈 보드, 최대 크기, 모든 명령 같은 방향) 직접 만들어 검증.

변형

1. 시간 가속 (Time Skipping)

T=10^9 인데 실제 변화는 N 회뿐이면, 변화 시점만 큐/배열로 모아서 O(N).

events = [(t1, change1), (t2, change2), ...]
sort(events)
for (t, change) in events:
    apply(change)

2. 주기 탐지 (Cycle Detection)

상태가 반복되면 나머지 연산으로 건너뛰기. 해시맵으로 state -> first_seen_time.

map<State, int> seen;
int cycle_start = -1, cycle_len = 0;
for (int t = 0; t < T; t++) {
    if (seen.count(state)) {
        cycle_start = seen[state];
        cycle_len = t - cycle_start;
        break;
    }
    seen[state] = t;
    state = next(state);
}
if (cycle_len > 0) {
    int remaining = (T - cycle_start) % cycle_len;
    // cycle_start 에서 remaining 단계 더 진행
}

3. 너비 우선 탐색 결합

이동 가능한 모든 위치를 BFS 로 탐색하며 시뮬레이션.

함정

1. 인덱스 1-indexed vs 0-indexed

문제가 “1행 1열” 이라면 입력도 1-indexed. 배열은 0-indexed. 변환 주의.

2. 경계 검사 누락

if (nx >= 0 && nx < N && ny >= 0 && ny < N) 빠뜨리면 segfault / 이상한 출력.

3. 명령 순서 바뀜

입력 순서 그대로 실행해야 하는데, 정렬하거나 역순으로 처리 → WA.

4. 동시 갱신 vs 순차 갱신

“모든 칸이 동시에 다음 상태로” 면 임시 배열 필요. “왼쪽부터 순서대로” 면 인플레이스. 문제 지문 정확히 읽기.

5. 시간 초과 (TLE)

T=10^9 를 단순 루프로 → 주기 탐지 또는 시간 가속 필요.

BOJ 연습 문제

참고

• 구현
• 너비 우선 탐색
• 격자
• 상태 기계