[ 백준 / BOJ 19237 ] 어른 상어 ( 자바 / JAVA )

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

19237번: 어른 상어

문제 설명

• 매 초마다 움직이며 냄새를 뿌리는 M마리의 상어 존재
• 각 상어들은 바라보는 방향과 기준에 따라 다음 움직일 방향 선택
  • 인접한 칸 중 아무 냄새가 없는 칸의 방향으로
  • 없다면, 자신의 냄세가 있는 칸의 방향으로
    • 이러한 칸들이 여러 개라면, 각 상어에 따른 특정한 우선순위를 따른다.
• 같은 격자에 들어가게 되면 번호가 작은 상어만 남음
• 1번 상어만 남기까지 걸리는 시간은??
• 1000초가 넘으면 -1

문제 풀이

Shark Class

---

• 상어의 좌표, 현재 뱡향을 갖음

remainingTimeOfSmell, sharkNumOfSmell, priorityOfDir, sharks

---

remainingTimeOfSmell : 각 칸 냄새의 남은 시간
sharkNumOfSmell : 각 칸 냄새의 상어의 번호
priorityOfDir : 각 상어의 방향별 우선순위
sharks : 상어들의 정보를 저장한 배열

Solve()

---

1. 남은 상어가 1마리라면 종료!
2. 시간이 1000초 지났다면 -1 출력 후 종료!
3. 둘다 아니라면 상어 움직이기
   3-1. moveShark(tmp, shark)

    3-1-1. 방향을 우선순위 순서대로 탐색하고, 범위 내고 냄새가 없다면 👉 flag = true 후, break
    3-1-2. 찾지 못한채 종료되면`if(!flag)`, 다시 본인 냄새를 찾기
    3-1-3. 1,2 둘 중에서 이동 가능한 칸을 찾앗다면, 이동
    3-1-4. 없다면, 상어 제거‼️

4. 냄새 시간 -1 시키기
5. tim += 1

코드

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

public class Main_BOJ_19237_어른_상어 {

    static class Shark{
        int x;
        int y;
        int dir;

        public Shark(int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }

    static int N, M, k;
    static int[][] remainingTimeOfSmell, sharkNumOfSmell;
    static int[][][] priorityOfDir;
    static Shark[] sharks;
    static int[] dx = {0, -1, 1, 0, 0};
    static int[] dy = {0, 0, 0, -1, 1};

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

        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        k = Integer.parseInt(stringTokenizer.nextToken());

        remainingTimeOfSmell = new int[N][N];
        sharkNumOfSmell = new int[N][N];
        priorityOfDir = new int[M + 1][5][4];
        sharks = new Shark[M + 1];

        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int tmp = Integer.parseInt(stringTokenizer.nextToken());
                if (tmp > 0) {
                    sharks[tmp] = new Shark(i, j, 0);
                    remainingTimeOfSmell[i][j] = k;
                    sharkNumOfSmell[i][j] = tmp;
                }
            }
        }

        stringTokenizer = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            sharks[i].dir = Integer.parseInt(stringTokenizer.nextToken());
        }

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= 4; j++) {
                stringTokenizer = new StringTokenizer(br.readLine());
                for (int l = 0; l < 4; l++) {
                    priorityOfDir[i][j][l] = Integer.parseInt(stringTokenizer.nextToken());
                }
            }
        }

        System.out.println(Solve());
    }

    private static int Solve() {
        int time = 0;

        while (true) {
            int cnt = 0;
            for (int i = 1; i <= M; i++) {
                if (sharks[i] != null) {
                    cnt += 1;
                }
            }

            if(cnt == 1 && sharks[1] != null) return time;
            if(time >= 1000) return -1;

            int[][] tmp = new int[N][N];
            for (int shark = 1; shark <= M; shark++) {
                if(sharks[shark] != null) moveShark(tmp, shark);
            }

            // 냄새 유효기간 하나씩 줄이기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if(remainingTimeOfSmell[i][j] > 0) remainingTimeOfSmell[i][j] -= 1;

                    if(remainingTimeOfSmell[i][j] == 0) sharkNumOfSmell[i][j] = 0;
                }
            }

            // 이동 후의 상어 위치의 냄새 정보와 유효기간 초기화하기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (tmp[i][j] > 0) {
                        remainingTimeOfSmell[i][j] = k;
                        sharkNumOfSmell[i][j] = tmp[i][j];
                    }
                }
            }

            time += 1;
        }
    }

    private static void moveShark(int[][] tmp, int shark) {
        int d = 0;
        int nx = 0;
        int ny = 0;
        boolean flag = false;

        // 1-1. 높은 우선순위부터 차례대로 탐색
        for (int i = 0; i < 4; i++) {
            d = priorityOfDir[shark][sharks[shark].dir][i];
            nx = sharks[shark].x + dx[d];
            ny = sharks[shark].y + dy[d];

            if(nx < 0 || ny < 0 || N <= nx || N <= ny) continue;
            if ((0 <= nx && nx < N) && (0 <= ny && ny < N) && sharkNumOfSmell[nx][ny] == 0) {
                flag = true;
                break;
            }
        }

        // 1-2. 냄새가 없는 곳이 없는 경우
        if (!flag) {
            for (int i = 0; i < 4; i++) {
                d = priorityOfDir[shark][sharks[shark].dir][i];
                nx = sharks[shark].x + dx[d];
                ny = sharks[shark].y + dy[d];

                if(nx < 0 || ny < 0 || N <= nx || N <= ny) continue;
                if ((0 <= nx && nx < N) && (0 <= ny && ny < N) && sharkNumOfSmell[nx][ny] == shark) break;
            }
        }

        if ((0 <= nx && nx < N) && (0 <= ny && ny < N) && tmp[nx][ny] == 0) {
            tmp[nx][ny] = shark;
            sharks[shark].x = nx;
            sharks[shark].y = ny;
            sharks[shark].dir = d;
        } else {
            sharks[shark] = null;
        }
    }
}