어른 상어

문제

19237번: 어른 상어

문제 설명

청소년 상어는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 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 ≤ N2, 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을 출력한다.

입출력 예

입력	출력
5 4 4
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3	14
4 2 6
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2
4 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3	26
5 4 1
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3	-1
5 4 10
0 0 0 0 3
0 0 0 0 0
1 2 0 0 0
0 0 0 0 4
0 0 0 0 0
4 4 3 1
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3	-1

입출력 예 설명

아이디어

제출 코드 (3/6까지 푼 내용)

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

public class two19237 {
    class Shark {
        int col;
        int row;
        int direction;
        int number;
        int timeStamp;
        int[][] position;

        int[][] dirPriority = new int[4][4];
        boolean isAlive;

        public Shark(int number, int timeStamp, int col, int row) {
            this.number = number;
            this.timeStamp = timeStamp;
            this.position = new int[timeStamp][2];
            for (int i = 0; i < timeStamp; i++) {
                Arrays.fill(this.position[i], -1);
            }
            this.position[0][0] = col;
            this.position[0][1] = row;
            this.isAlive = true;
            this.col = col;
            this.row = row;
        }

        public void setDirection(int direction) {
            this.direction = direction;
        }

        public void setDirPriority(int[][] dirPriority) {
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    this.dirPriority[i][j] = dirPriority[i][j];
                }
            }
        }

        public void print() {
            System.out.println("direction = " + direction);
            System.out.println("number = " + number);
            System.out.println("timeStamp = " + timeStamp);
            System.out.println();
            System.out.println("position");
            for (int[] row : position) {
                System.out.println(Arrays.toString(row));
            }
            System.out.println();
            System.out.println("dir priority");
            for (int[] row : dirPriority) {
                System.out.println(Arrays.toString(row));
            }
            System.out.println();
            System.out.println();
            System.out.println();
        }

        public void move(int nextCol, int nextRow, int direction) {
            this.direction = direction;
            for (int i = timeStamp - 1; i > 0; i--) {
                position[i][0] = position[i - 1][0];
                position[i][1] = position[i - 1][1];
            }
            position[0][0] = nextCol;
            position[0][1] = nextRow;
            this.col = nextCol;
            this.row = nextRow;
        }

        public void dead(int col, int row) {
            this.col = col;
            this.row = row;
        }
    }

    // 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽
    public int[] dCol = {-1, 1, 0, 0};
    public int[] dRow = {0, 0, -1, 1};
    public int n, m, k;
    public int[][] map;
    public Shark[] sharks;

    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(infoToken.nextToken());
        m = Integer.parseInt(infoToken.nextToken());
        k = Integer.parseInt(infoToken.nextToken());

        map = new int[n][n];
        sharks = new Shark[m];

        // 지도와 상어 입력
        for (int i = 0; i < n; i++) {
            StringTokenizer mapToken = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(mapToken.nextToken());
                if (map[i][j] != 0) {
                    sharks[map[i][j] - 1] = new Shark(map[i][j], k, i, j);
                }
            }
        }

        // 상어 방향 세팅
        StringTokenizer directionToken = new StringTokenizer(reader.readLine());
        for (int i = 0; i < m; i++) {
            sharks[i].setDirection(Integer.parseInt(directionToken.nextToken()) - 1);
        }

        // 상어 방향 우선순위 세팅
        int[][] temp = new int[4][4];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 4; j++) {
                StringTokenizer priorityToken = new StringTokenizer(reader.readLine());
                for (int l = 0; l < 4; l++) {
                    temp[j][l] = Integer.parseInt(priorityToken.nextToken()) - 1;
                }
            }
            sharks[i].setDirPriority(temp);
        }

        int time = 0;

        while (!oneLive()) {
            time++;
            moveShark();
            if (time >= 1000) {
                time = -1;
                break;
            }
        }
        System.out.println(time);
    }

    private boolean oneLive() {
        for (int i = 1; i < m; i++) {
            if (sharks[i].isAlive) return false;
        }
        return true;
    }

    private void moveShark() {
        for (int current = 0; current < m; current++) {
            Shark shark = sharks[current];
            // 죽었다면 패스
            if (!shark.isAlive) {
                shark.move(-1, -1, -1);
                if (shark.position[k - 1][0] != -1 && shark.position[k - 1][1] != -1) {
                    map[shark.position[k - 1][0]][shark.position[k - 1][1]] = 0;
                }
                continue;
            }
            int[] moveDir = shark.dirPriority[shark.direction];

            boolean canMove = false;
            for (int i = 0; i < 4; i++) {
                if (!shark.isAlive) break;
                int nextCol = shark.col + dCol[moveDir[i]];
                int nextRow = shark.row + dRow[moveDir[i]];
                // 범위 밖이라면 패스
                if (nextCol < 0 || nextCol >= n || nextRow < 0 || nextRow >= n) continue;
                // 다른 상어 향기
                boolean isSharked = false;
                if (map[nextCol][nextRow] != 0) {
                    // 상어가 있는 경우
                    for (int j = 0; j < current; j++) {
                        if (sharks[j].col == nextCol && sharks[j].row == nextRow) {
                            shark.isAlive = false;
                            shark.dead(-1, -1);
                            isSharked = true;
                            canMove = true;
                            break;
                        }
                    }
                    // 향기만 있는 경우
                    if (!isSharked) continue;
                }
                if (isSharked) break;

                // 마지막 향기 제거 후 새 향기 추가
                if (shark.position[k - 1][0] != -1) {
                    map[shark.position[k - 1][0]][shark.position[k - 1][1]] = 0;
                }
                map[nextCol][nextRow] = shark.number;
                shark.move(nextCol, nextRow, moveDir[i]);
                canMove = true;
                break;
            }
            if (!canMove) {
                int nextCol = 0;
                int nextRow = 0;
                int direction = 0;
                int[] directions = shark.dirPriority[shark.direction];
                for (int i = 0; i < 4; i++) {
                    nextCol = shark.col + dCol[directions[i]];
                    nextRow = shark.row + dRow[directions[i]];
                    if (nextCol < 0 || nextCol >= n || nextRow < 0 || nextRow >= n) continue;
                    if (map[nextCol][nextRow] == shark.number) {
                        direction = directions[i];
                        break;
                    }
                }
                // 마지막 향기 제거 후 새 향기 추가
                if (shark.position[k - 1][0] != -1) {
                    map[shark.position[k - 1][0]][shark.position[k - 1][1]] = 0;
                }
                map[nextCol][nextRow] = shark.number;

                shark.move(nextCol, nextRow, direction);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        new two19237().solution();
    }
}

테스트 케이스 2 분석

상어 1		상어 2
↑	↑ ↓ ← →	↑	↑ ↓ ← →
↓	↓ ← → ↑	↓	↓ ← → ↑
←	← → ↑ ↓	←	← → ↑ ↓
→	→ ↑ ↓ ←	→	→ ↑ ↓ ←

1(6) →	0	0	0
0	0	0	0
0	0	0	0
0	0	0	2(6) ←

1(5)	1(6) →	0	0
0	0	0	0
0	0	0	0
0	0	2(6) ←	2(5)

1(3)	1(4)	1(5)	1(6) →
0	0	0	0
0	0	0	0
2(6) ←	2(5)	2(4)	2(3)

1(2)	1(3)	1(4)	1(5)
0	0	0	1(6) ↓
2(6) ↑	0	0	0
2(5)	2(4)	2(3)	2(2)

1(1)	1(2)	1(3)	1(4)
2(6) ↑	0	0	1(5)
2(5)	0	0	1(6) ↓
2(4)	2(3)	2(2)	2(1)

2(6) ↑	1(1)	1(2)	1(3)
2(5)	0	0	1(4)
2(4)	0	0	1(5)
2(3)	2(2)	2(1)	1(6) ↓

여기서 문제 발생 1이 2(1) 자리로 내려올 때 시점에는 1의 향기가 제거되지 않은 것처럼 코드가 짜여져서

상어들이 이동하기 전에 향기를 먼저 다 제거해야 함

재제출 코드

import java.io.*;

public class two19237 {
    static int N, M, k;
    static int[][] resttime;
    static int[][] smell;
    static int[][][] priority;
    static Shark[] shark;
    static int[] dr = {0, -1, 1, 0, 0};
    static int[] dc = {0, 0, 0, -1, 1};

    public void solution() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        k = Integer.parseInt(input[2]);

        resttime = new int[N + 1][N + 1];
        smell = new int[N + 1][N + 1];
        priority = new int[M + 1][5][4];
        shark = new Shark[M + 1];

        for (int i = 1; i <= N; i++) {
            input = br.readLine().split(" ");
            for (int j = 1; j <= N; j++) {
                int n = Integer.parseInt(input[j - 1]);

                if (n > 0) {
                    shark[n] = new Shark(i, j, 0);
                    resttime[i][j] = k;
                    smell[i][j] = n;
                }
            }
        }
        input = br.readLine().split(" ");
        for (int i = 1; i <= M; i++)
            shark[i].d = Integer.parseInt(input[i - 1]);

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= 4; j++) {
                input = br.readLine().split(" ");
                for (int k = 0; k < 4; k++) {
                    priority[i][j][k] = Integer.parseInt(input[k]);
                }
            }
        }

        bw.write(solve() + "\n");
        bw.flush();

    }

    public static int solve() {

        int time = 0;

        while (true) {

            int count = 0;
            for (int m = 1; m <= M; m++) {
                if (shark[m] != null)
                    count++;
            }

            if (count == 1 && shark[1] != null) { // 1번 상어 혼자 남은 경우
                return time;
            }

            if (time >= 1000)
                return -1;

            int[][] tmp = new int[N + 1][N + 1];

            for (int m = 1; m <= M; m++) {

                if (shark[m] != null) { // 상어가 경계 안에 있다면
                    moveShark(tmp, m);
                }
            }

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

                    if (resttime[i][j] == 0)
                        smell[i][j] = 0;
                }
            }

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

    }

    public static void moveShark(int[][] tmp, int m) {

        int nr = 0;
        int nc = 0;
        int d = 0;

        boolean flag = false;

        // 1-1. 높은 우선순위부터 차례대로 탐색
        for (int i = 0; i < 4; i++) {

            d = priority[m][shark[m].d][i];
            nr = shark[m].r + dr[d];
            nc = shark[m].c + dc[d];

            // 경계를 벗어나지 않으면서, 냄새가 없는 곳을 찾으면 break로 빠져나옴
            if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && smell[nr][nc] == 0) {
                flag = true;
                break;
            }
        }

        // 1-2. 냄새가 없는 곳이 없는 경우
        if (!flag) {
            for (int i = 0; i < 4; i++) {

                d = priority[m][shark[m].d][i];
                nr = shark[m].r + dr[d];
                nc = shark[m].c + dc[d];

                if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && smell[nr][nc] == m)
                    break;
            }
        }

        if (tmp[nr][nc] == 0) {

            tmp[nr][nc] = m;
            shark[m].r = nr;
            shark[m].c = nc;
            shark[m].d = d;
        } else {
            shark[m] = null;
        }

    }

    static class Shark {

        int r, c, d;

        Shark(int r, int c, int d) {
            this.r = r;
            this.c = c;
            this.d = d;
        }
    }

    public static void main(String[] args) throws IOException {
        new two19237().solution();
    }
}