[백준/BOJ] 19237 어른 상어 - JAVA

문제

https://www.acmicpc.net/problem/19237

문제 분석

조건

`N×N`격자 중 M개의 칸에 상어가 한 마리씩 들어있다. 상어는 시작 위치에 냄새를 뿌린다. 모든 상어는 1초마다 상하좌우로 인접한 칸으로 이동하고, 이동한 칸에도 냄새를 뿌린다. 냄새는 `k`초 후에 사라진다.

상어가 이동할 때는 현재 바라보는 방향에서 냄새가 없는 칸으로 이동한다. 인접한 칸에 이동할 수 있는 칸이 여러 군데면 우선순위를 따른다. 냄새가 없는 칸이 없다면 자신의 냄새가 있는 곳으로 이동한다. 이 역시 우선순위를 따른다.

같은 칸에 상어가 여러 마리 존재할 경우 작은 번호의 상어만 남고, 나머지 상어는 없어진다.

풀이방법

상어 클래스를 정의하여 `상어의 위치, 번호, 방향, 생존 여부, 바라보는 방향에 따른 우선순위`를 관리하였다. 지금까지 푸는 상어 문제들은 공통적으로 조건과 상태관리만 주의한다면 풀이 자체는 단순 구현에 가깝다.

같은 칸에 상어가 여러 마리 존재한다면 작은 번호의 상어만 남으므로 처음부터 1번 상어부터 이동하도록 하였다. 그 후에 뒷번호 상어가 이동하려는 칸에 이미 다른 상어가 존재한다면, 앞번호 상어가 이미 차지한 자리이므로 바로 죽은 상어로 처리하였다.

if (map[nextR][nextC][SMELL_REMAIN] == 0) {    // 냄새가 없음
    if (map[nextR][nextC][SHARK_NUM] != 0) { // 같은 턴에 앞번호 상어가 이동한 칸임
        shark.isAlive = false;
        sharkCount--;
        map[shark.r][shark.c][SHARK_NUM] = 0;

이때 냄새가 없는 칸만 검사한 이유는 이전 턴에 자리를 차지한(아직 이동하지 않은) 상어가 있는 자리는 제외하기 위해서이다. 그리고 이렇게 구현하기 위해서는 상어가 이동했을 때 바로 상어 위치에 상어의 냄새를 뿌리면 안 된다. 상어의 냄새는 냄새 감소 부분에서 상어가 위치한 칸이면 `k`값의 냄새를 뿌리고, 상어가 없이 냄새가 남아있을 땐 냄새를 감소시키며 구현했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Shark {
        int r, c, num, nowDir;
        boolean isAlive;
        int[][] dirPriority;

        public Shark(int r, int c, int num) {
            this.r = r;
            this.c = c;
            this.num = num;
            this.isAlive = true;
            this.dirPriority = new int[4][4];
        }

        public void setNowDir(int nowDir) {
            this.nowDir = nowDir;
        }

        public void setDirPriority(int dir, int[] priority) {
            this.dirPriority[dir] = priority;
        }
    }

    static int N, M, k;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int SHARK_NUM = 0, SMELL_REMAIN = 1, SMELL_SHARK = 2;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int[][][] map = new int[N][N][3];   // [r][c][상어 번호, 냄새, 냄새 남긴 상어]
        Shark[] sharks = new Shark[M + 1];
        int sharkCount = M;

        // 지도 입력
        for (int r = 0; r < N; r++) {
            st = new StringTokenizer(br.readLine());
            for (int c = 0; c < N; c++) {
                map[r][c][SHARK_NUM] = Integer.parseInt(st.nextToken());
                if (map[r][c][SHARK_NUM] != 0) {    // 상어일 경우
                    map[r][c][SMELL_REMAIN] = k;
                    map[r][c][SMELL_SHARK] = map[r][c][SHARK_NUM];
                    sharks[map[r][c][SHARK_NUM]] = new Shark(r, c, map[r][c][SHARK_NUM]);
                }
            }
        }

        // 상어 방향
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            sharks[i].setNowDir(Integer.parseInt(st.nextToken()) - 1);
        }

        // 상어 이동 우선순위 입력
        for (int shark = 1; shark <= M; shark++) {
            for (int dir = 0; dir < 4; dir++) {
                st = new StringTokenizer(br.readLine());
                int[] priority = new int[4];
                for (int i = 0; i < 4; i++) {
                    priority[i] = Integer.parseInt(st.nextToken()) - 1;
                }
                sharks[shark].setDirPriority(dir, priority);
            }
        }

        int answer = 0;
        while (sharkCount != 1) {
            answer++;
            if (answer > 1000) {
                answer = -1;
                break;
            }

            // 상어 움직임
            for (Shark shark : sharks) {    // 작은 번호의 상어만 남기기 위해 1번부터 이동
                if (shark == null) {
                    continue;
                }
                if (!shark.isAlive) {
                    continue;
                }
                int[] dirPriority = shark.dirPriority[shark.nowDir];
                boolean moveCheck = false;
                for (int dir : dirPriority) {   // 인접한 칸에 빈 칸 있음
                    int nextR = shark.r + dirs[dir][0];
                    int nextC = shark.c + dirs[dir][1];
                    if (isOutOfBounds(nextR, nextC)) {
                        continue;
                    }
                    if (map[nextR][nextC][SMELL_REMAIN] == 0) {    // 냄새가 없음
                        if (map[nextR][nextC][SHARK_NUM] != 0) { // 같은 턴에 앞번호 상어가 이동한 칸임
                            shark.isAlive = false;
                            sharkCount--;
                            map[shark.r][shark.c][SHARK_NUM] = 0;
                        } else {
                            sharkMove(map, shark, dir, nextR, nextC);
                        }
                        moveCheck = true;
                        break;
                    }
                }
                if (moveCheck) {
                    continue;
                }
                // 인접한 칸에 빈칸 없었음 -> 내 냄새칸으로
                for (int dir : dirPriority) {
                    int nextR = shark.r + dirs[dir][0];
                    int nextC = shark.c + dirs[dir][1];
                    if (isOutOfBounds(nextR, nextC)) {
                        continue;
                    }
                    if (map[nextR][nextC][SMELL_SHARK] == shark.num) {    // 본인 냄새가 있는 칸
                        sharkMove(map, shark, dir, nextR, nextC);
                        break;
                    }

                }
            }
            // 냄새 감소
            fadeSmell(map);
        }
        System.out.println(answer);
    }

    private static boolean isOutOfBounds(int nextR, int nextC) {
        return nextR < 0 || nextC < 0 || nextR >= N || nextC >= N;
    }

    private static void fadeSmell(int[][][] map) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (map[r][c][SHARK_NUM] != 0) {    // 지금 상어가 있는 칸임
                    map[r][c][SMELL_REMAIN] = k;
                } else if (map[r][c][SMELL_REMAIN] > 0) {
                    map[r][c][SMELL_REMAIN]--;
                    if (map[r][c][SMELL_REMAIN] == 0) {
                        map[r][c][SMELL_SHARK] = 0;
                    }
                }
            }
        }
    }

    private static void sharkMove(int[][][] map, Shark shark, int dir, int nextR, int nextC) {
        // 기존 위치 비우기
        map[shark.r][shark.c][SHARK_NUM] = 0;
        shark.r = nextR;
        shark.c = nextC;
        //새 위치에 상어번호 넣기
        map[nextR][nextC][SHARK_NUM] = shark.num;
        map[nextR][nextC][SMELL_SHARK] = shark.num;
        shark.nowDir = dir;
    }
}

주절주절

2년 전에 제출 기록이 있어서 정답 코드를 제출하며 두근두근했다. 예전보다 못했으면 어떡하지!

휴우우우ㅋㅋㅋ 다행. 메모리도 줄이고 시간도 줄였다! 예전 코드 다시 확인해 보니 죽은 상어도 계속 배열 돌면서 확인하고, 클래스를 상어가 아닌 `Smell`클래스를 만들어서 구현을 해놨었다. 근데 코드를 살펴보니 그렇게 엉망인 거 같지도 않고..? 그래서 GPT에게 비교를 부탁했다.

지피티 말로는 예전코드는 배열 중심으로 구현했고, 지금은 객체중심으로 코드를 구현했다고 했다. 그러면서 갑자기 내 예전 코드의 단점들을 뽑아주더니... 비교도 해주고 총평도 해준다. 아주 기똥차다.