🤖 시뮬레이션 & 구현

1️⃣ 개념

"문제에서 주어진 규칙을 시간의 흐름 또는 단계에 따라 그대로 재현하는 유형"

시뮬레이션 문제는 알고리즘 이론보다 상태 관리와 구현 능력이 중요합니다.

보통 이런 특징이 있습니다.

• 여러 객체가 동시에 움직임
• 시간 또는 턴 단위 진행
• 상태가 계속 변화
• 규칙이 많고 디테일함

현실 상황을 코드로 그대로 재현하는 문제

2️⃣ 핵심 특징

3️⃣ 예시 문재: 🔥 불이 퍼지는 시뮬레이션

📌 문제 설명

• 2차원 격자가 있다.
• 불이 붙은 칸은 매 초마다 상하좌우로 번진다.
• 벽은 불이 번지지 않는다.
• 모든 칸이 불타는데 걸리는 시간을 구하라

🧐 예시

초기 상태

0 1 0
0 0 0
1 0 0

1 = 불
0 = 빈칸

진행 과정

1초 후
1 1 1
0 1 0
1 1 0

2초 후
1 1 1
1 1 1
1 1 1

4️⃣ 핵심 아이디어

시뮬레이션 문제는 보통 이렇게 설계합니다.

🔹 상태 저장 구조

현재 격자 상태

🔹 진행 루프

시간 증가
→ 모든 객체 상태 업데이트
→ 충돌 / 확산 처리
→ 종료 조건 확인

5️⃣ 예시 풀이 (BFS 기반 시뮬레이션)

function fireSpread(grid) {
	const n = grid.length;
	const m = grid[0].length;
	const queue = [];

	// 처음 불이 난 위치를 모두 큐에 넣고 BFS 시작
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < m; j++) {
			if (grid[i][j] === 1) {
				queue.push([i, j, 0]); // x좌표, y좌표, 시간
			}
		}
	}

	const dirs = [
		[1, 0],
		[-1, 0],
		[0, 1],
		[0, -1]
	];

	let maxTime = 0;

	while (queue.length) {
		const [x, y, time] = queue.shift();
		maxTime = Math.max(maxTime, time); // 가장 늦게 불난 시간 저장

		for (let [dx, dy] of dirs) {
			const nx = x + dx;
			const ny = y + dy;

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 좌표를 벗어나는 경우
			if (grid[nx][ny] !== 0) continue; // 이미 불이 붙은 경우

			grid[nx][ny] = 1;
			queue.push([nx, ny, time + 1]);
		}
	}

	return maxTime;
}

✍️ 한 줄 정리

시뮬레이션 문제는 "시간의 흐름에 따라 상태를 정확히 관리하며 규칙을 그대로 구현하는 문제 유형"