2차원 배열에서 동시 이동 (코드트리 숫자가 가장 큰 인접한 곳으로 동시에 이동)

https://www.codetree.ai/ko/external-connection/classes/177/lectures/1766/curated-cards/intro-move-to-max-adjacent-cell-simultaneously/description

Codetree: Master Coding Interviews - Data Structures & Algorithms

문제 분석

• M 개의 구슬이 서로 다른 위치에서 시작해서 1초에 한 번씩 상하좌우로 인접한 곳에 있는 숫자들 중 가장 큰 값이 적혀있는 숫자가 있는 위치로 동시에 이동한다.
• 가장 큰 값이 적힌 위치가 여러 개 있는 경우 상하좌우 방향 순서대로 우선순위를 매기고 더 높은 곳으로 이동한다.
• 이동한 이후 2개의 구슬의 위치가 같으면 충돌하여 사라진다.

문제 풀이

먼저 구슬이 있는 위치를 저장하는 ball 배열과 격자 정보를 저장하는 board 배열을 입력 받는다.

동시 이동을 처리하려면?

"모든 구슬이 동시에" 움직인다. 만약 원본 ball 배열에 직접 이동 결과를 기록하면, 아직 움직이지 않은 구슬의 위치를 덮어쓰거나, 방금 이동한 구슬을 또 이동시킬 수도 있다. 그래서 다음 시간 (t + 1) 에 구슬들이 도착할 위치를 미리 그려보고자 nextBall 이라는 임시 배열을 사용한다. 즉 총 3개의 배열을 사용한다!

배열 이름	역할	비유
board	지형의 점수 (고정)	지도 (바뀌지 않는 길)
ball	현재 구슬들의 위치	현재 사진 (판단의 근거)
nextBall	다음 시간의 구슬 위치	설계도

일단 탐색하는 함수 (move)

1. ball 배열에서 구슬이 있는 위치를 찾는다.
2. 만약에 구슬을 발견하면, moveBall 을 호출하여 다음 칸을 계산하고, nextBall 에 표시한다.
3. 모든 구슬이 nextBall 로 이동을 마친 뒤 값이 2 이상 (구슬이 충돌) 인 칸을 찾아 0으로 비운다.
4. ball = nextBall 을 통해 갱신한다.  (얕은 복사)

// 이동 함수
static void move() {
    // 이동 후를 담을 임시 배열
    int[][] nextBall = new int[n][n];

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (ball[r][c] == 1) { // 구슬이 있다면
                moveBall(r, c, nextBall);
            }
        }
    }

    // 충돌 처리
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (nextBall[r][c] > 1) {
                nextBall[r][c] = 0;
            }
        }
    }
    ball = nextBall; // 현재 상태 업데이트

}

구슬이 갈 곳 정하기 (moveBall)

1. maxVal 에 갱신 
2. 탐색 시 가장 큰 값이 있는 칸으로 이동하며, 값이 같을 경우 상하좌우 순으로 우선순위가 매겨진다. 
3. 구슬을 찾으면 nextBall[targetR][targetC] ++ 를 해줘서 구슬 개수를 카운트 한다.

단순히 nr, nc 로 바로 바로 이동하는 것이 아니라 4 방향 모두 탐색했을 때 가장 값이 큰 칸으로 이동해야 하기 때문에 가장 값이 큰 칸의 좌표를 target 에 저장해서 관리한다.

static void moveBall(int r, int c, int[][] nextBall) {
    int maxVal = Integer.MIN_VALUE;
    int targetR = r, targetC = c; // 기본은 제자리

    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (inRange(nr, nc)) {
            if (board[nr][nc] > maxVal) {
                maxVal = board[nr][nc];
                targetR = nr;
                targetC = nc;
            }
        }
    }
    nextBall[targetR][targetC]++; // 이동한 곳에 구슬을 추가

}

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    static int n, m, t;
    // 상하좌우
    static int[] dr = {-1, 1, 0, 0}; // 행 변화량
    static int[] dc = {0, 0, -1, 1}; // 열 변화량

    static int[][] board, ball; // 격자, 구슬 위치

    static boolean inRange(int r, int c){
        return r >= 0 && r < n && c >= 0 && c < n;
    }

    // 이동 함수
    static void move(){
        // 이동 후를 담을 임시 배열
        int[][] nextBall = new int[n][n];

        for(int r = 0; r < n; r++){
            for(int c = 0; c < n; c++){
                if(ball[r][c] == 1) { // 구슬이 있다면
                    moveBall(r, c, nextBall); 
                }
            }
        }

        // 충돌 처리
        for(int r = 0; r < n; r++){
            for(int c = 0; c < n; c++){
                if(nextBall[r][c] > 1) {
                    nextBall[r][c] = 0;
                }
            }
        }
        ball = nextBall; // 현재 상태 업데이트

    }

    static void moveBall(int r, int c, int[][] nextBall){
        int maxVal = Integer.MIN_VALUE;
        int targetR = r, targetC = c; // 기본은 제자리

        for(int d = 0; d < 4; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(inRange(nr, nc)){
                if(board[nr][nc] > maxVal){
                    maxVal = board[nr][nc];
                    targetR = nr;
                    targetC = nc;
                }
            }
        }
        nextBall[targetR][targetC] ++; // 이동한 곳에 구슬을 추가

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); // 격자 크기
        m = Integer.parseInt(st.nextToken()); // 구슬 개수
        t = Integer.parseInt(st.nextToken()); // 시간

        board = new int[n][n];
        ball = new int[n][n];

        // 격자 입력
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 구슬 위치 입력
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            ball[r - 1][c - 1] = 1; // 1-based
        }

        while(t --> 0){
            move();
        }

        int ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(ball[i][j] == 1) ans ++;
            }
        }
        System.out.print(ans);

    }
}