코드트리 [자바 java] 숫자가 가장 큰 인접한 곳으로 동시에 이동

https://www.codetree.ai/missions/2/problems/move-to-max-adjacent-cell-simultaneously/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

배열에 있는 수들과 그 곳에 위치한 구슬들이 존재할 때 해당 조건에 맞게 구슬을 움직이고, 마지막에 남은 구슬의 갯수를 구하는 문제이다.

 

• 구슬들의 위치를 입력받을 때 이를 다른 배열에 저장해두지 않고, 새로운 격자를 만들어 해당 위치에 1로 표시했는데 이는 구슬이 겹쳐졌을 때 없애는 조치를 취하기 쉽고, 나중에 구슬의 갯수를 셀 때 모두 더하면 되니까 편리하다.
• 구슬 주변의 숫자를 탐색할 때 dx,xy테크닉을 사용했는데,  dx,dy 배열을 만들 때 문제에서 제시한 우선순위(상하좌우)를 고려하였다.

 

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


public class Main {

    static int[][] arr;
    static int[][] mar;
    static int n;

    //구슬 움직이기

    static void move(){
        int[][] newmar = new int[n+1][n+1];
       

        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(mar[i][j] == 1){

                    int max = 0;
                    int mx = 0;
                    int my = 0;

                    for(int k = 0;k<4;k++){
                        if( i + dx[k] >= 1 && i + dx[k] <= n &&
                            j + dy[k] >= 1 && j + dy[k] <= n && max < arr[i + dx[k]][j + dy[k]]){
                            mx = i + dx[k];
                            my = j + dy[k];
                            max = arr[i + dx[k]][j + dy[k]];
                        }

                    }

                    newmar[mx][my] += 1;

                }
            }
        }

         for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                mar[i][j] = newmar[i][j];
            }
        }
        remove();
    }

    // 겹치는 구슬 없애기

    static void remove(){
        for(int i = 1;i<=n;i++){
           
            for(int j = 1;j<=n;j++){
                
               if(mar[i][j] >= 2){
                mar[i][j] = 0;
               }
            }
        }
    }



    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());
        int m = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());
        
         arr = new int[n+1][n+1];
         mar = new int[n+1][n+1];

        for(int i = 1;i<=n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j =1;j<=n;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i =0;i<m;i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            mar[a][b] = 1;
        }

        for(int i = 0;i<t;i++){
            move();
        }

        int ans = 0;
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                ans += mar[i][j];
            }
        }

        System.out.println(ans);
    }
}