백준 19237

Java/코딩테스트

백준 19237

Bubbles 2023. 10. 12. 23:54

🦈 백준 19237 : 어른 상어

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

19237번: 어른 상어

첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미

www.acmicpc.net

🦈 생각보다 괜찮게 풀었던 문제. 마법사 상어와 복제마법 문제와 로직이 어느정도 겹치는 느낌이 있다. (냄새 배열을 3차원으로 만드는 것 등)

🦈 Static 변수들

// 상 : 0, 하 : 1, 좌 : 2, 우 : 3
private static int[] dirX = { -1, 1, 0, 0 }; // 상하좌우 순
private static int[] dirY = { 0, 0, -1, 1 };
private static int[][] map;
private static int[][][] order;
private static int[][][] smell;
private static int n, m, k, sharkCount;
private static ArrayList<Pos>[] sharkPos;

* 참고로 방향 넣을 때 -1해서 넣어줘야 한다. (문제의 입력은 1부터 시작하므로)

🦈 메인 로직

makeSmell() : 냄새를 자기가 있는 칸에 남긴다. 상어 좌표정보 리스트를 돌면서, 살아있는 상어라면 해당 칸에 k만큼 냄새 남기기

private static void makeSmell() {
    for (int i = 1; i <= m; i++) {
        if (!sharkPos[i].isEmpty())
            smell[sharkPos[i].get(0).x][sharkPos[i].get(0).y][i] = k;
    }
}

moveShark() : 상어를 움직인다.
- ArrayList<Pos>[] sharkPos : 상어의 위치정보
- int [ i ][ d ][ ] order : 각 상어의 우선순위 배열, i번째 상어가 현재 d 방향일때의 각 우선순위를 담은 3차원 배열이다.
- 이미 죽은 상어라면 넘기고, 살아있다면 우선순위에 맞게 탐색한다.
  - 좌표가 유효한지 검사 isValid()
  - 냄새 검사
    - smell [ x ] [ y ] [ i ] : x , y 좌표에 i번째 상어의 냄새가 있는지 여부
    - 즉, 상어 개수만큼 마지막 i에 대해 for문 돌려줘야 한다.
  - 냄새가 없는 칸을 발견하면 해당 칸으로 이동한다. map[x][y] = 0, map[nextX][nextY] = 상어번호, sharkPos 갱신
    - 다른 상어가 있다면 번호를 비교한 후 번호가 더 큰 상어는 없애기
      - sharkPos[bigger].remove(0);
      - map 갱신
  - 다 냄새가 있다면 findOwnSmell ( int index , Pos pos )

private static void moveShark() {
    for (int i = 1; i<=m; i++) {
        if (sharkPos[i].isEmpty() || sharkPos[i].size() == 0) {
            continue;
        }
        Pos pos = sharkPos[i].get(0);

        boolean find = false;
        int x = pos.x;
        int y = pos.y;
        int dir = pos.dir;

        for (int j = 0; j < 4; j++) {
            int nextX = x + dirX[order[i][dir][j]];
            int nextY = y + dirY[order[i][dir][j]];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            int smellCount = 0;
            for (int s = 1; s <= m; s++) {
                if (smell[nextX][nextY][s] == 0) {
                    smellCount++;
                }
            }

            if (smellCount == m) { // 냄새가 없는 칸이라면
                find = true;
                // 칸에 다른 상어도 없는 경우
                if (map[nextX][nextY] == 0) {
                    sharkPos[i].set(0, new Pos(nextX, nextY, order[i][dir][j]));
                    map[nextX][nextY] = i;
                    map[pos.x][pos.y] = 0;
                } else {
                    // 다르 상어가 있다면
                    if (map[nextX][nextY] > i) { // 나보다 약한애라면
                        sharkPos[i].set(0, new Pos(nextX, nextY, order[i][dir][j]));
                        sharkPos[map[nextX][nextY]].remove(0);
                        map[nextX][nextY] = i;
                        map[pos.x][pos.y] = 0;
                    } else { // 나보다 강한애라면
                        map[pos.x][pos.y] = 0;
                        sharkCount--;
                        sharkPos[i].remove(0);
                    }
                }
                break;
            }
        }

        if (!find) {
            // 자기 냄새 있는 칸 찾기
            findOwnSmell(i, pos);
        }
    }
}

findOwnSmell( int index, Pos pos )
- pos 기준, order대로 4방향 탐색을 하면된다.
- 움직인 후 map 갱신

private static void findOwnSmell(int index, Pos pos) {
    int dir = pos.dir;
    int x = pos.x;
    int y = pos.y;

    for (int i = 0; i < 4; i++) {
        int nextX = x + dirX[order[index][dir][i]];
        int nextY = y + dirY[order[index][dir][i]];

        if (!isValid(nextX, nextY)) {
            continue;
        }

        if (smell[nextX][nextY][index] > 0) {
            sharkPos[index].set(0, new Pos(nextX, nextY, order[index][dir][i]));
            map[x][y]= 0;
            map[nextX][nextY] = index;
            return;
        }
    }
}

removeSmell() : 냄새 제거

private static void removeSmell() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int s = 1; s <= m; s++) {
                if (smell[i][j][s] > 0) {
                    smell[i][j][s]--;
                }
            }
        }
    }
}

🦈 전체 코드

import java.util.*;
import java.io.*;
public class p19237 {
    // 상 : 0, 하 : 1, 좌 : 2, 우 : 3
    private static int[] dirX = { -1, 1, 0, 0 }; // 상하좌우 순
    private static int[] dirY = { 0, 0, -1, 1 };
    private static int[][] map;
    private static int[][][] order;
    private static int[][][] smell;
    private static int n, m, k, sharkCount;
    private static ArrayList<Pos>[] sharkPos;

    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];
        order = new int[m+1][4][4];
        smell = new int[n][n][m+1];
        sharkPos = new ArrayList[m+1];
        sharkCount = m;
        int time = 0;

        for (int i = 0; i <= m; i++) {
            sharkPos[i] = 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) {
                    sharkPos[map[i][j]].add(new Pos(i, j, 0));
                }
            }
        }

        // 상어들의 초기 방향
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            int dir = Integer.parseInt(st.nextToken());
            sharkPos[i].set(0, new Pos(sharkPos[i].get(0).x, sharkPos[i].get(0).y, dir-1));
        }

        for (int i = 1; i <= m; i++) {
            // i번째 상어의 우선순위 인풋
            for (int d = 0; d < 4; d++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++) {
                    // 방향 0부터 시작하므로 -1해준다.
                    order[i][d][j] = Integer.parseInt(st.nextToken()) - 1;
                }
            }
        }

        while (sharkCount > 1 && time <= 1000) {
            magic();
            time++;
        }

        if (time > 1000) {
            System.out.println(-1);
        } else {
            System.out.println(time);
        }

    }

    private static void magic() {
         makeSmell();
         moveShark();
         removeSmell();
    }

    private static void moveShark() {
        for (int i = 1; i<=m; i++) {
            if (sharkPos[i].isEmpty() || sharkPos[i].size() == 0) {
                continue;
            }
            Pos pos = sharkPos[i].get(0);

            boolean find = false;
            int x = pos.x;
            int y = pos.y;
            int dir = pos.dir;

            for (int j = 0; j < 4; j++) {
                int nextX = x + dirX[order[i][dir][j]];
                int nextY = y + dirY[order[i][dir][j]];

                if (!isValid(nextX, nextY)) {
                    continue;
                }

                int smellCount = 0;
                for (int s = 1; s <= m; s++) {
                    if (smell[nextX][nextY][s] == 0) {
                        smellCount++;
                    }
                }

                if (smellCount == m) { // 냄새가 없는 칸이라면
                    find = true;
                    // 칸에 다른 상어도 없는 경우
                    if (map[nextX][nextY] == 0) {
                        sharkPos[i].set(0, new Pos(nextX, nextY, order[i][dir][j]));
                        map[nextX][nextY] = i;
                        map[pos.x][pos.y] = 0;
                    } else {
                        // 다르 상어가 있다면
                        if (map[nextX][nextY] > i) { // 나보다 약한애라면
                            sharkPos[i].set(0, new Pos(nextX, nextY, order[i][dir][j]));
                            sharkPos[map[nextX][nextY]].remove(0);
                            map[nextX][nextY] = i;
                            map[pos.x][pos.y] = 0;
                        } else { // 나보다 강한애라면
                            map[pos.x][pos.y] = 0;
                            sharkCount--;
                            sharkPos[i].remove(0);
                        }
                    }
                    break;
                }
            }

            if (!find) {
                // 자기 냄새 있는 칸 찾기
                findOwnSmell(i, pos);
            }
        }
    }

    private static void findOwnSmell(int index, Pos pos) {
        int dir = pos.dir;
        int x = pos.x;
        int y = pos.y;

        for (int i = 0; i < 4; i++) {
            int nextX = x + dirX[order[index][dir][i]];
            int nextY = y + dirY[order[index][dir][i]];

            if (!isValid(nextX, nextY)) {
                continue;
            }

            if (smell[nextX][nextY][index] > 0) {
                sharkPos[index].set(0, new Pos(nextX, nextY, order[index][dir][i]));
                map[x][y]= 0;
                map[nextX][nextY] = index;
                return;
            }
        }
    }

    private static void makeSmell() {
        for (int i = 1; i <= m; i++) {
            if (!sharkPos[i].isEmpty())
                smell[sharkPos[i].get(0).x][sharkPos[i].get(0).y][i] = k;
        }
    }

    private static void removeSmell() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int s = 1; s <= m; s++) {
                    if (smell[i][j][s] > 0) {
                        smell[i][j][s]--;
                    }
                }
            }
        }
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= n) {
            return false;
        }
        return true;
    }
    static class Pos {
        int x;
        int y;
        int dir;
        Pos (int x, int y, int dir) {
            this.x = x;
            this.y = y;
            this.dir = dir;
        }
    }
}