구현 (Implementation)

정의

구현 (Implementation) 은 PS 에서 알고리즘적 난이도는 낮지만 정확한 코딩이 필요한 문제 유형. 주로 시뮬레이션 (simulation), 조건 분기 (conditional logic), edge case 처리 가 핵심. solved.ac 에서 두 번째로 많은 문제를 포함하는 범용 태그 (1위는 수학).

특별한 알고리즘 없이 문제 지문을 그대로 코드로 옮기는 작업이지만, off-by-one 에러, 좌표 변환 실수, 경계 처리 누락 등 디테일 실수가 많다.

문제 상황과 동기

구현 태그 문제는 다음 세 범주로 나뉜다.

1. 시뮬레이션: 주어진 규칙대로 상태를 갱신. 예: 게임판 이동, 로봇 청소기, 뱀.
2. 조건 분기: 여러 경우를 if-else 로 분류. 예: 윤년 판정, 사분면, 점수 등급.
3. 문자열/배열 조작: 회전, 뒤집기, 정렬 후 출력.

핵심 통찰: 문제 지문이 곧 스펙. 요구사항을 빠뜨리지 않고 정확히 구현하는 것이 전부.

실무 / PS 위치: 실무에서 가장 많은 시간을 소비하는 작업. 알고리즘보다 버그 없는 구현이 중요.

시각화

핵심 아이디어

1. 상태 관리

시뮬레이션 문제는 상태 변수 (state) 를 명시적으로 관리.

struct Robot {
    int x, y, dir;   // 위치 + 방향
};

각 step 에서 상태를 갱신하고, 종료 조건을 체크.

2. 방향 벡터 (Direction Vector)

상하좌우 이동은 배열로 표현.

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 북, 남, 서, 동

for (int d = 0; d < 4; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (0 <= nx && nx < N && 0 <= ny && ny < M) {
        // 유효 범위
    }
}

3. Edge Case 체크리스트

4. Off-by-One 방지

1-indexed vs 0-indexed, <= N vs < N, [l, r) vs [l, r] 일관성.

// 1-indexed 입력 -> 0-indexed 배열
for (int i = 1; i <= N; i++) {
    cin >> a[i - 1];
}

알고리즘

시뮬레이션 템플릿

state = initial_state
while not done:
    state = update(state)
    if termination_condition(state):
        break
return result(state)

경계 검사 (Bounds Check)

is_valid(x, y):
    return 0 <= x < N and 0 <= y < M

회전 변환 (2D)

rotate_90_cw(x, y, N):   # N×N 격자
    return (y, N - 1 - x)

구현

// 시뮬레이션: 로봇 청소기 (간단한 예)
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  int N, M, x, y, dir;
  cin >> N >> M >> x >> y >> dir;   // 격자 크기, 시작 위치, 방향 (북0 동1 남2 서3)
  vector<vector<int>> grid(N, vector<int>(M));
  for (auto& row : grid) for (auto& v : row) cin >> v;   // 0=깨끗, 1=벽
  
  int dx[] = {-1, 0, 1, 0};   // 북, 동, 남, 서
  int dy[] = {0, 1, 0, -1};
  int cleaned = 0;
  
  while (true) {
      if (grid[x][y] == 0) {
          grid[x][y] = 2;   // 청소 완료
          cleaned++;
      }
      bool found = false;
      for (int i = 0; i < 4; i++) {
          dir = (dir + 3) % 4;   // 반시계 회전
          int nx = x + dx[dir], ny = y + dy[dir];
          if (0 <= nx && nx < N && 0 <= ny && ny < M && grid[nx][ny] == 0) {
              x = nx; y = ny;
              found = true;
              break;
          }
      }
      if (!found) {   // 후진
          int back = (dir + 2) % 4;
          int nx = x + dx[back], ny = y + dy[back];
          if (nx < 0 || nx >= N || ny < 0 || ny >= M || grid[nx][ny] == 1) break;
          x = nx; y = ny;
      }
  }
  cout << cleaned << "\n";
}

# 시뮬레이션: 로봇 청소기
N, M, x, y, dir = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(N)]
​
dx = [-1, 0, 1, 0]   # 북, 동, 남, 서
dy = [0, 1, 0, -1]
cleaned = 0
​
while True:
  if grid[x][y] == 0:
      grid[x][y] = 2
      cleaned += 1
  found = False
  for _ in range(4):
      dir = (dir + 3) % 4
      nx, ny = x + dx[dir], y + dy[dir]
      if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] == 0:
          x, y = nx, ny
          found = True
          break
  if not found:
      back = (dir + 2) % 4
      nx, ny = x + dx[back], y + dy[back]
      if not (0 <= nx < N and 0 <= ny < M) or grid[nx][ny] == 1:
          break
      x, y = nx, ny
print(cleaned)

// 시뮬레이션: 로봇 청소기
import java.util.*;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt(), M = sc.nextInt();
      int x = sc.nextInt(), y = sc.nextInt(), dir = sc.nextInt();
      int[][] grid = new int[N][M];
      for (int i = 0; i < N; i++)
          for (int j = 0; j < M; j++)
              grid[i][j] = sc.nextInt();
      
      int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
      int cleaned = 0;
      
      while (true) {
          if (grid[x][y] == 0) {
              grid[x][y] = 2;
              cleaned++;
          }
          boolean found = false;
          for (int i = 0; i < 4; i++) {
              dir = (dir + 3) % 4;
              int nx = x + dx[dir], ny = y + dy[dir];
              if (0 <= nx && nx < N && 0 <= ny && ny < M && grid[nx][ny] == 0) {
                  x = nx; y = ny;
                  found = true;
                  break;
              }
          }
          if (!found) {
              int back = (dir + 2) % 4;
              int nx = x + dx[back], ny = y + dy[back];
              if (nx < 0 || nx >= N || ny < 0 || ny >= M || grid[nx][ny] == 1) break;
              x = nx; y = ny;
          }
      }
      System.out.println(cleaned);
  }
}

3 3 1 1 0
1 1 1
1 0 1
1 1 1

1

11 10 7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

57

복잡도

대부분 O(N) 또는 O(N^2) 이내. 10^6 이상은 시뮬레이션보다 최적화 필요.

변형 / 활용

함정

1. Off-by-One 에러

// WRONG: i <= N (배열 범위 초과)
for (int i = 0; i <= N; i++) a[i] = 0;

// RIGHT: i < N
for (int i = 0; i < N; i++) a[i] = 0;

<= vs <, N-1 vs N, 1-indexed 입력 vs 0-indexed 배열.

2. 방향 벡터 순서

// 북, 동, 남, 서 (시계방향)
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

문제에서 요구하는 방향 순서와 일치해야 함. 북=0, 동=1, 남=2, 서=3 인지 확인.

3. 좌표 변환 실수

// 2D 배열 회전 90도 시계방향 (N×N)
// (x, y) -> (y, N - 1 - x)
int nx = y, ny = N - 1 - x;

회전/뒤집기 공식을 정확히. 반시계는 (N - 1 - y, x).

4. 종료 조건 누락

무한 루프에 빠지지 않도록 종료 조건 명시. 예: 모든 칸 방문, 시간 초과, 더 이상 이동 불가.

5. Edge Case 미흡

N=1, 빈 입력, 모든 칸이 벽, 시작 위치가 벽 등.

BOJ 연습 문제

참고

• 시뮬레이션
• 백트래킹
• 너비 우선 탐색
• 깊이 우선 탐색