[코드트리/INTERMEDIATE LOW] 숫자가 가장 큰 인접한 곳으로 동시에 이동 (JAVA)

📖 문제

 

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

 

 

💡  풀이 방식

• 시뮬레이션

필요 자료구조
-  인접한 칸들 접근 위한 상하좌우 dx/dy 배열
- 숫자 입력받을 2차원 int형 배열 (grid)
- 구슬 갯수 표시하는 2차원 int형 배열 (cntArr)
- 구슬 이동 변화 발생 후의 구슬 위치와 갯수를 나타내는 2차원 int형 배열 (nextCnt) ✅

 

1. NxN 크기의 배열에 모든 숫자를 입력받는다.

2. M개의 구슬 위치를 나타내는 입력 (r,c)을 받아 구슬 위치 배열을 채운다..

3. T초 동안 = T번 아래 동작을 반복한다.

    3-1. 각 위치에서의 구슬의 개수를 나타내는 nextCnt 배열을 0으로 초기화한다.

    3-2. 완전탐색을 통해 모든 점에서 구슬을 전부 숫자가 가장 큰 인접한 곳으로 이동시킨다. (move 메소드)

    3-3. 구슬 이동 후 완성된 nextCnt 배열의 값들을 현재의 구슬 위치와 개수로 나타내도록 cntArr로 복사한다.

           이 때, 칸에서 구슬의 갯수가 2개 이상인 경우 충돌이 난 것이므로 0 처리한다.

for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= N ; j++) {
        cntArr[i][j] = nextCnt[i][j];

        // 충돌이 일어난 구슬 처리
        if(cntArr[i][j] >= 2) {
            cntArr[i][j] = 0;
        }
    }
}

 

 

4. 현재 구슬의 수와 위치를 담은 cntArr를 돌며 총 남아있는 구슬 수를 구한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};   // 우선순위 : 상하좌우
    static int[] dy = {0, 0, -1, 1};
 
    static int N, M, T;
    static int[][] grid, cntArr, nextCnt;   // 격자 | 구슬 갯수 배열 | 구슬 이동이 일어난 후의 구슬 갯수 배열
    static int answer = 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());   // 격자 크기
        M = Integer.parseInt(st.nextToken());   // 구슬 개수
        T = Integer.parseInt(st.nextToken());   // 시간
 
        grid = 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++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        // 구슬 위치 배열 채우기
        cntArr = new int[N + 1][N + 1];
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
 
            cntArr[r][c] = 1;
        }
 
        while(T --> 0) {
            // 1. 각 위치에서의 구슬 개수를 나타내는 nextCnt 배열 초기화
            nextCnt = new int[N + 1][N + 1];
 
            // 2. 모든 점에서 구슬 전부 한 번씩 움직여보기
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    if(cntArr[i][j] == 1) {
                        move(i, j);
                    }
                }
            }
 
            // 3. nextCnt 값을 cntArr에 복사
            for(int i = 1 ; i <= N ; i++) {
                for(int j = 1 ; j <= N ; j++) {
                    cntArr[i][j] = nextCnt[i][j];
 
                    // 충돌이 일어난 구슬 처리
                    if(cntArr[i][j] >= 2) {
                        cntArr[i][j] = 0;
                    }
                }
            }
        }
 
        // 남아있는 구슬 수 출력
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(cntArr[i][j] == 1) {
                    answer++;
                }
            }
        }
 
        System.out.println(answer);
    }
 
    private static void move(int x, int y) {

        int[] nextPos = getNextPos(x, y);
 
        int nx = nextPos[0];
        int ny = nextPos[1];
 
        nextCnt[nx][ny] += 1;   // 그 다음 위치에 구슬 개수 +1
    }

 
// 인접한 곳들 중 가장 값이 큰 위치 찾는 메소드
    private static int[] getNextPos(int x, int y) {
        int[] pos = new int[2];
        int max = 0;
 
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if(!inRange(nx, ny))    continue;
 
            if(grid[nx][ny] > max) {
                max = grid[nx][ny];
                pos = new int[]{nx, ny};
            }
        }
 
        return pos;
    }
 
    private static boolean inRange(int x, int y) {
        return (1 <= x && x <= N && 1 <= y && y <= N);
    }
}

 

 

 

---

💦 어려웠던 점

- 2차원 int형 배열 nextCnt를 생성해서 사용할 생각은 이번에 학습하지 않았다면 혼자 생각하기 어려웠을 것 같다.

매 구슬이 있는 위치마다 구슬을 이동시키고 난 결과를 갖고 그 값을 활용하기 위해 생성한 배열이니까 매 초마다 초기화해줘야하기도 하고..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 코드트리 격자 안에서 여러 객체를 이동