[backjoon]19237 어른 상어 java

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

19237번: 어른 상어

빡구현 문제! 

이 문제에서 요구하는 것은 세 가지라고 생각한다. 
1. 상어의 이동 2. 냄새의 관리 3. 상어자체에 대한 정보 관리(방향, 현재 상태) 
이 세가지가 유기적으로 관련되어 있어서 하나가 꼬이면 더럿 꼬이는 것 같다. 
초기화 과정이 매우 긴 것도 문제를 헷갈리게 하는 것 같다. 

문제 풀이

1. 상어의 이동

1) 현재 방향의 우선 순위에 맞게 탐색한다. 상어의 이동중에서 방향이 바뀐다면 그 방향을 상어의 정보에 반영한다.

2) 다른 상어의 냄새이 있다면 그 방향은 피한다.

3) 내가 온 방향이 있기 때문에 못 가는 방향은 없다.

4) 해당 칸에 이미 다른 상어가 있고 그 상어가 현재 상어보다 숫자가 크다면 무시한다. -> 바로바로 반영하지 않고 이동 값을 모아둔 후 한 번에 반영한다.

2. 냄새의 관리

1) 이동이 끝나면 냄새가 1씩 감소한다.

사용한 자료 구조

- 상어의 위치를 관리할 2차원 배열

- 상어 자체를 관리할 자료 구조

- 상어의 흔적(냄새)을 관리할 2차원 배열 2개(하나는 흔적 관리,  하나는 시간 관리) 

- 상어의 현재 위치를 파악할 2차원 배열(흔적 관리용 2차원 배열을 바탕으로 만듦)

- 상어의 방향에 따른 탐색 우선 순위를 관리할 2차원 배열

풀이 구성

spread : 상어가 움직임을 완료한 후 냄새 관리

move : 상어의 움직임 구현

state : 상어의 상태 파악

 

코드

import java.io.*;
import java.util.*;
 
class Main {
    static int[][] map, scent, timer;
    static int N, M, k, cnt;
    static Shark[] sharks;
    static int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
 
    public static void main(String[] args) throws Exception {
        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());
        map = new int[N][N];
        timer = new int[N][N];
        scent = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] != 0) {
                    timer[i][j] = k;
                    scent[i][j] = map[i][j];
                }
            }
        }
        sharks = new Shark[M + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            int dir = Integer.parseInt(st.nextToken()) - 1;
            sharks[i] = new Shark(i, dir);
        }
        for (int i = 1; i <= M; i++) {
            int[][] priorityDir = new int[4][4];
            for (int j = 0; j < 4; j++) {
                st = new StringTokenizer(br.readLine());
                for (int d = 0; d < 4; d++) {
                    int dir = Integer.parseInt(st.nextToken()) - 1;
                    priorityDir[j][d] = dir;
                }
            }
            sharks[i].move = priorityDir;
        }
 
        // << 상어가 움직이는 과정 - 이동할 위치를 정한다 -> 냄새를 뿌린다. -> 쫓아낸다. >>
        int sec = -1;
        while (sec++ < 1000) {
            int[][] position = state();
            move(position);
            if (cnt == 1)
                break;
        }
        if (cnt != 1)
            sec = -1;
        
        System.out.println(sec);
    }
 
    //상어가 남긴 냄새 관리 이동 직후에 이뤄지고, 시간이 다 되었으면 냄새 부분을 0으로 초기화.
    public static void spread() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (timer[i][j] == 0)
                    continue;
                timer[i][j]--;
                if (timer[i][j] == 0)
                    scent[i][j] = 0;
            }
        }
    }
 
    // 상어의 움직임 파악하는 부분
    public static void move(int[][] position) {
        Queue<int[]> queue = new LinkedList<>();
        for (int i = M; i > 0; i--) {
            Shark curShark = sharks[i];
            int[] pos = position[i]; // r, c
            boolean flag = false;
            if (pos[0] == -1 && pos[1] == -1)
                continue;
            // 주변에 다른 상어의 냄새 확인
            for (int d = 0; d < 4; d++) {
                int curD = curShark.move[curShark.dir][d];
                int nextR = pos[0] + dirs[curD][0];
                int nextC = pos[1] + dirs[curD][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) continue;
                if (scent[nextR][nextC] == 0) {
                    map[pos[0]][pos[1]] = 0;
                    queue.add(new int[] { nextR, nextC, i, curD });
                    flag = true;
                    break;
                }
 
            }
            // 주변에 다른 상어의 냄새가 없어서 이동할 수 있다면 더 탐색하지 않음.
            if (flag)    continue;
 
            // 주변에 다른 상어의 냄새가 있으면 내 방향을 탐색한다.
            for (int d = 0; d < 4; d++) {
                int curD = curShark.move[curShark.dir][d];
                int nextR = pos[0] + dirs[curD][0];
                int nextC = pos[1] + dirs[curD][1];
                if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N)    continue;
                if (scent[nextR][nextC] == i) {
                    map[pos[0]][pos[1]] = 0;
                    queue.add(new int[] { nextR, nextC, i, curD });
                    break;
                }
            }
        }
 
        spread();
 
        // 새로운 상어 정보 반영 -> 역순으로 탐색해서  값이 중복되면 자연스럽게 작은 값이 들어게게  코딩.
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            map[cur[0]][cur[1]] = cur[2];
            scent[cur[0]][cur[1]] = cur[2];
            timer[cur[0]][cur[1]] = k;
            sharks[cur[2]].dir = cur[3];
 
        }
    }
 
    // 현재 상태 기록 용도 init
    // 현재 상어의 위치를 파악해서 배열에 담아준다. 값이 없다면 -1로 초기화해서 불필요한 탐색을 줄임.
    public static int[][] state() {
        cnt = 0;
        int[][] result = new int[M + 1][2];
        for (int i = 0; i < M + 1; i++) {
            result[i][0] = -1;
            result[i][1] = -1;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 0)    continue;
                result[map[i][j]][0] = i;
                result[map[i][j]][1] = j;
                cnt++;
            }
        }
 
        return result;
    }
 
    public static class Shark {
        int idx;
        int dir;
        int[][] move = new int[4][4];
 
        Shark(int idx, int dir) {
            this.idx = idx;
            this.dir = dir;
        }
    }
}

 

막상 코드를 보면 복잡한 것 같지 않은데 설명하는게 어렵다 ㅠ