[백준] 19237 - 어른 상어 (자바 Java)

[Gold II] 어른 상어 - 19237

문제 링크

성능 요약

메모리: 19676 KB, 시간: 152 ms

분류

구현(implementation), 시뮬레이션(simulation)

문제 설명

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다.

N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다. 냄새는 상어가 k번 이동하고 나면 사라진다.

각 상어가 이동 방향을 결정할 때는, 먼저 인접한 칸 중 아무 냄새가 없는 칸의 방향으로 잡는다. 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 이때 가능한 칸이 여러 개일 수 있는데, 그 경우에는 특정한 우선순위를 따른다. 우선순위는 상어마다 다를 수 있고, 같은 상어라도 현재 상어가 보고 있는 방향에 따라 또 다를 수 있다. 상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

모든 상어가 이동한 후 한 칸에 여러 마리의 상어가 남아 있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자 밖으로 쫓겨난다.

<그림 1>

우선 순위
상어 1		상어 2		상어 3		상어 4
↑	↓ ← ↑ →	↑	↓ → ← ↑	↑	→ ← ↓ ↑	↑	← → ↑ ↓
↓	→ ↑ ↓ ←	↓	↓ ↑ ← →	↓	↑ → ← ↓	↓	← ↓ → ↑
←	← → ↓ ↑	←	← → ↑ ↓	←	↑ ← ↓ →	←	↑ → ↓ ←
→	→ ← ↑ ↓	→	→ ↑ ↓ ←	→	← ↓ ↑ →	→	↑ → ↓ ←

<표 1>

<그림 1>은 맨 처음에 모든 상어가 자신의 냄새를 뿌린 상태를 나타내며, <표 1>에는 각 상어 및 현재 방향에 따른 우선순위가 표시되어 있다. 이 예제에서는 k = 4이다. 왼쪽 하단에 적힌 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 좌측 상단에 적힌 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호를 의미한다.

<그림 2>

<그림 3>

<그림 2>는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태이고, <그림 3>은 <그림 2>의 상태에서 한 칸 더 이동한 것이다. (2, 4)에는 상어 2과 4가 같이 도달했기 때문에, 상어 4는 격자 밖으로 쫓겨났다.

<그림 4>

<그림 5>

<그림 4>은 격자에 남아있는 모든 상어가 한 칸 이동하고 자신의 냄새를 뿌린 상태, <그림 5>는 <그림 4>에서 한 칸 더 이동한 상태를 나타낸다. 상어 2는 인접한 칸 중에 아무 냄새도 없는 칸이 없으므로 자신의 냄새가 들어있는 (2, 4)으로 이동했다. 상어가 이동한 후에, 맨 처음에 각 상어가 뿌린 냄새는 사라졌다.

이 과정을 반복할 때, 1번 상어만 격자에 남게 되기까지 몇 초가 걸리는지를 구하는 프로그램을 작성하시오.

입력

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N², 1 ≤ k ≤ 1,000)

그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미한다.

그 다음 줄에는 각 상어의 방향이 차례대로 주어진다. 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미한다.

그 다음 줄부터 각 상어의 방향 우선순위가 상어 당 4줄씩 차례대로 주어진다. 각 줄은 4개의 수로 이루어져 있다. 하나의 상어를 나타내는 네 줄 중 첫 번째 줄은 해당 상어가 위를 향할 때의 방향 우선순위, 두 번째 줄은 아래를 향할 때의 우선순위, 세 번째 줄은 왼쪽을 향할 때의 우선순위, 네 번째 줄은 오른쪽을 향할 때의 우선순위이다. 각 우선순위에는 1부터 4까지의 자연수가 한 번씩 나타난다. 가장 먼저 나오는 방향이 최우선이다. 예를 들어, 우선순위가 1 3 2 4라면, 방향의 순서는 위, 왼쪽, 아래, 오른쪽이다.

맨 처음에는 각 상어마다 인접한 빈 칸이 존재한다. 따라서 처음부터 이동을 못 하는 경우는 없다.

출력

1번 상어만 격자에 남게 되기까지 걸리는 시간을 출력한다. 단, 1,000초가 넘어도 다른 상어가 격자에 남아 있으면 -1을 출력한다.

 

---

풀이

구현 문제는 조건을 꼼꼼히 확인하고 단계별로 차근차근 구현하면 어렵지는 않은 것 같다

개인적으로 청소년 상어보다 쉬웠음.. 배열 복사가 많지 않아서 그런건가

각주에 풀이를 달아두긴 했는데 과정은 다음과 같다.

처음에 상어 냄새 뿌리기(while문 밖)

상어 이동 -> 상어 냄새 뿌리기 -> K번이 지난 냄새 사라지기 -> 1만 남았는지 검사 -> cnt 증가

상어 냄새를 뿌릴 때 낮은 번호의 상어가 우위를 가지기 때문에 상어 번호가 큰 순서대로 검사하였다.

상어가 사라진다면 Shark 클래스에서 removed를 true로 바꿨다.

 

상어가 이동할 때는 상어의 r과 c, 그리고 방향을 바꿔줘야 한다.

그리고 냄새의 생명주기를 기록할 배열을 새로 만들고 Smell 클래스를 선언하였다.

package BOJ.Gold.g2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class BOJ_19237_어른상어 {

    static class Shark implements Comparable<Shark> {
        int r; // r좌표
        int c; // c좌표
        int num; // 번호
        int dir; // 방향
        int[][] priority; // 우선순위 배열
        boolean removed;
        // 방향은 1,2,3,4 위 아래 왼 오

        public Shark(int r, int c, int num) {
            this.r = r;
            this.c = c;
            this.num = num;
            removed = false;

        }

        @Override
        public int compareTo(Shark o) {
            return this.num - o.num;
        }

        @Override
        public String toString() {
            return "Shark{" +
                    "r=" + r +
                    ", c=" + c +
                    ", num=" + num +
                    ", dir=" + dir +
                    ", priority=" + Arrays.deepToString(priority) +
                    '}';
        }
    }

    static class Smell {
        int val; // 몇 번 상어의 냄새인지
        int life; // 몇 번 남았는지 -> k가 되면 삭제

        public Smell(int val, int life) {
            this.val = val;
            this.life = life;
        }
    }


    static int N; // N*N격자
    static int M; // 상어 번호
    static int K; // 상어는 k번이동

    static int[][] map; // N*N
    static Smell[][] smells;

    static List<Shark> sharks;

    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, -1, 1};


    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());
        map = new int[N][N];
        smells = new Smell[N][N]; // 냄새 기록
        sharks = new ArrayList<>();
        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) {
                    sharks.add(new Shark(i, j, map[i][j]));
                }
            }
        }

        // 입력

        Collections.sort(sharks); // 번호 순 정렬
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            // 상어 방향
            sharks.get(i).dir = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            Shark s = sharks.get(i);
            int[][] priority = new int[5][4]; //[향하는 방향(1~4)][우선순위 방향]
            for (int d = 1; d <= 4; d++) {
                st = new StringTokenizer(br.readLine());
                for (int p = 0; p < 4; p++) {
                    priority[d][p] = Integer.parseInt(st.nextToken());
                }
            }
            s.priority = priority;
            sharks.set(i, s);
        }

        // map은 상어들의 위치


        int cnt = 0;

        for (int i = M - 1; i >= 0; i--) {
            Shark s = sharks.get(i);
            smells[s.r][s.c] = new Smell(s.num, K); // 처음 상태의 냄새 기록
        }
        while (cnt <= 1000) {
            // 1. 현재 냄새 뿌리기

            // 2. 이동
            int[][] tmp = new int[N][N];
            for (int i = M - 1; i >= 0; i--) {
                Shark s = sharks.get(i);
                if (s.removed) continue; // 제거됐으면 안봄
                int[] priority = s.priority[s.dir]; // 현재 방향의 우선순위 배열 
                boolean isEmpty = false; 
                for (int d = 0; d < 4; d++) {
                    int dir = priority[d]; // 이동할 후보 보기
                    int nr = s.r + dr[dir];
                    int nc = s.c + dc[dir];
                    if (nr >= 0 && nr < N && nc >= 0 && nc < N && smells[nr][nc] == null) {
                        isEmpty = true;
                        // 이미 tmp가 있으면 걔 없애고 작은 애가 위치함
                        if (tmp[nr][nc] != 0) {
                            sharks.get(tmp[nr][nc] - 1).removed = true;
                        }
                        tmp[nr][nc] = s.num;


                        s.r = nr;
                        s.c = nc;
                        s.dir = dir;
                        break;
                    }
                }
                if (!isEmpty) {
                    // 자기 자신의 냄새가 있는 곳으로 이동
                    for (int d = 0; d < 4; d++) {
                        int dir = priority[d]; // 이동할 후보 보기
                        int nr = s.r + dr[dir];
                        int nc = s.c + dc[dir];
                        if (nr >= 0 && nr < N && nc >= 0 && nc < N && smells[nr][nc] != null && smells[nr][nc].val == s.num) {
                            tmp[nr][nc] = s.num;
                            s.r = nr;
                            s.c = nc;
                            s.dir = dir;
                            break;
                        }
                    }
                }

            }

            // map을 tmp로 바꾸기
            // 3. 1만 남았는지 확인
            boolean onlyOne = true;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++) {
                    // 없어질 냄새 확인
                    if (smells[i][j] != null) {
                        Smell smell = smells[i][j];

                        smell.life--;
                        if (smell.life == 0) {
                            smells[i][j] = null;
                        }
                    }
                    // 1만 남았는지 확인
                    if (map[i][j] != 0 && map[i][j] != 1) {
                        onlyOne = false;
                    }

                    // map과 smell에 추가
                    map[i][j] = tmp[i][j];
                    if (map[i][j] != 0) {
                        smells[i][j] = new Smell(map[i][j], K);
                    }
                }
            if (onlyOne) {
                System.out.println(cnt);
                return;
            }


            // 1000초가 넘어도 남아있으면 -1

            cnt++;
        }

        System.out.println(-1);

    }
}