동블

그래프 뷰

01. 구현-시뮬레이션

4 min read

구현 / 시뮬레이션

Summary

삼성/SWEA/카카오 초중반 문제는 알고리즘보다 구현 실수가 더 자주 터진다.
격자 이동, 배열 복사, 회전, 동시 처리, 단계 진행을 먼저 고정한다.

자주 나오는 신호

문제 신호처리
격자에서 객체가 움직임방향 배열 + 범위 체크
매 초/매 턴 상태 변화새 배열에 다음 상태 기록
동시에 이동결과 배열 또는 충돌 카운트 배열 사용
배열 회전새 배열에 좌표 변환
원본 보존 필요2차원 deep copy
벽 세우고 탐색조합 + BFS

90도 회전 + 2차원 deep copy 검증 템플릿

Info

copy = board.clone()은 2차원 배열에서 얕은 복사다.
행마다 clone()해야 한다.

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] board = new int[n][n];
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        int[][] rotated = rotateRight(board);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(rotated[i][j]);
                if (j < n - 1) sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
 
    static int[][] rotateRight(int[][] board) {
        int n = board.length;
        int[][] result = new int[n][n];
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = board[i][j];
            }
        }
 
        return result;
    }
 
    static int[][] copyBoard(int[][] board) {
        int n = board.length;
        int[][] copy = new int[n][];
        for (int i = 0; i < n; i++) {
            copy[i] = board[i].clone();
        }
        return copy;
    }
}

좌표 이동 기본

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
 
for (int dir = 0; dir < 4; dir++) {
    int nx = x + dx[dir];
    int ny = y + dy[dir];
 
    if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
    // 이동 처리
}

동시 처리 원칙

Warning

한 객체를 움직이자마자 원본 배열을 바꾸면 뒤 객체 판단이 꼬일 수 있다.

1. 현재 board를 기준으로 모든 객체의 이동 후보를 계산한다.
2. nextBoard 또는 countBoard에 결과를 기록한다.
3. 충돌/삭제/합체를 처리한다.
4. board = nextBoard로 교체한다.

엣지케이스

N = 1, M = 1
객체가 하나도 없음
모든 칸이 벽
동시에 같은 칸으로 이동
이동 후 범위 밖
회전 횟수가 4의 배수
원본 배열을 다음 경우에도 재사용해야 함

백지 복원

1. 2차원 배열 deep copy 코드를 써라.
2. 90도 오른쪽 회전 좌표식은?
3. 동시 이동 문제에서 원본 배열을 바로 바꾸면 왜 위험한가?
4. 격자 범위 체크 조건을 직접 써라.

관련 문서