[Java] 백준 19237번 - 어른 상어

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

19237번: 어른 상어

----------------------------------------------------------------------------------------------------------------------

[문제 풀이]

 

문제가 엄청 길어서 복잡할줄 알았는데, 차근차근 읽어보니 단순 구현이라 생각보다 어렵지는 않았습니다.

- start[]에 각 상어의 시작 방향을 저장

- priority[][][] 배열에 상어들의 우선순위를 저장

- shark[] 상어들의 현재 위치 저장 배열

- sharkNum[][] 해당 위치에 냄새를 뿌려둔 상어 저장

- timeLeft[][] 냄새가 사라지기까지 남은 시간

예제 1번을 위의 배열들을 사용하여 살펴보자면, 우선 4개의 상어의 시작위치를  shark[]에 저장합니다.

처음 위치된 상어들은 냄새가 4초동안 유지되므로, 상어 (i,j) 위치를 저장하고, 남은시간은 4로 초기화 해줍니다.

마지막으로 상어의 현재 방향과, 방향 우선순위를 저장합니다.

 

- move()

4개의 상어들이 움직일수 있는 위치로 이동합니다. 만약 냄새가 없는 장소가 없다면, 가까운 자신의 냄새로 이동합니다.

1, 2, 3, 4 순서로 이동을 하던 도중, 해당 위치에 이미 이동된 상어가 있다면 이전에 이동됐던 상어에게 잡아먹힙니다.

( 1~4순으로 이동시키기 때문에 새로 들어오는 상어는 이전상어보다 우선순위가 낮을 수밖에 없습니다. )

 

- nextTime()

상어를 이동시킨 후, 상어들의 냄새의 남은시간을 갱신하여 줍니다.

 

이러한 작업들을 반복하며 1번 상어만 남은 시간을 출력하면 됩니다.

 

[정답 코드]

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

class Shark {
    int x;
    int y;
    Shark(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
// 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽
public class Main {
    public static int N; // N*N 보드
    public static int M; // M개의 상어
    public static int k; // K번 이동!
    public static int start[]; // 각 상어의 시작 방향
    public static int priority[][][];
    public static int dx[] = {0, -1, 1, 0, 0};
    public static int dy[] = {0, 0, 0, -1, 1};
    public static Shark shark[]; // 상어들의 위치
    public static int sharkNum[][]; // 냄새 뿌린 상어
    public static int timeLeft[][]; // 남은 시간
    public static int time = 0;
    public static int cnt = 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());
        k = Integer.parseInt(st.nextToken());
        cnt = M;
        start = new int[M + 1];
        shark = new Shark[M + 1];
        priority = new int[M + 1][5][5];
        sharkNum = new int[N][N];
        timeLeft = new int[N][N];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                int num = Integer.parseInt(st.nextToken());
                if(num > 0) {
                    shark[num] = new Shark(i,j);
                    sharkNum[i][j] = num;
                    timeLeft[i][j] = k;
                }
            }
        }
        st = new StringTokenizer(br.readLine());
        for(int i=1;i<=M;i++) {
            start[i] = Integer.parseInt(st.nextToken());
        }
        // M개의 상어 우선순위 다 넣음
        for(int i=1;i<=M;i++) {
            for(int j=1;j<=4;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=1;k<=4;k++) {
                    priority[i][j][k] = Integer.parseInt(st.nextToken());
                }
            }
        }
        while(time < 1000) {
            move(); // 4개의 상어를 이동시킴
            nextTime();
            time++;
            if(cnt == 1) {
                System.out.println(time);
                System.exit(0);
            }
        }
        System.out.println(-1);
    }
    public static void move() {
        // 4개의 상어를 이동시킴
        for(int i=1;i<=M;i++) {
            // i번째 상어 이동
            boolean isFind = false;
            if(shark[i] != null) {
                int now = start[i]; // 현재 상어가 보고 있는 방향
                for(int j=1;j<=4;j++) {
                    int next = priority[i][now][j];
                    int nextX = shark[i].x + dx[next];
                    int nextY = shark[i].y + dy[next];
                    if(!checkOut(nextX, nextY) && sharkNum[nextX][nextY] == 0) {
                        // 겹치는 상어 죽이기
                        if(outShark(i, nextX, nextY)) {
                            shark[i] = null;
                            cnt--;
                        } else {
                            start[i] = next;
                            shark[i] = new Shark(nextX, nextY);
                        }
                        isFind = true;
                        break;
                    }
                }
                // 자신이 냄새 뿌린 곳으로 돌아가기
                if(!isFind) {
                    for(int j=1;j<=4;j++) {
                        int next = priority[i][now][j];
                        int nextX = shark[i].x + dx[next];
                        int nextY = shark[i].y + dy[next];
                        if(!checkOut(nextX, nextY) && sharkNum[nextX][nextY] == i) {
                            start[i] = next;
                            shark[i] = new Shark(nextX, nextY);
                            break;
                        }
                    }
                }
            }
        }
    }
    public static boolean checkOut(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= N) {
            return true;
        }
        return false;
    }
    public static void nextTime() {
        for(int i=0;i<N;i++) {
            for(int j=0;j<N;j++) {
                if(timeLeft[i][j] == 1) {
                    timeLeft[i][j] = 0;
                    sharkNum[i][j] = 0;
                }
                if(timeLeft[i][j] > 1) {
                    timeLeft[i][j] = timeLeft[i][j] - 1;
                }
            }
        }
        for(int i=1;i<=M;i++) {
            if(shark[i] == null) {
                continue;
            }
            int x = shark[i].x;
            int y = shark[i].y;
            sharkNum[x][y] = i;
            timeLeft[x][y] = k;
        }
    }
    public static boolean outShark(int num, int x, int y) {
        for(int i=1;i<num;i++) {
            if(shark[i] != null && shark[i].x == x && shark[i].y == y) {
                return true;
            }
        }
        return false;
    }
}