[백준] 19237. 어른 상어

April 22, 2021 6 분 소요

문제 링크

[백준] 19237. 어른 상어

풀이 과정

시뮬레이션 문제입니다. 3시간 정도 헤맨 것 같습니다.. 문제를 풀면서 변수명은 최대한 헷갈리지 않게 의미를 부여하며 작성했습니다.

유의할 점들은 다음과 같습니다.

냄새와 그 냄새를 뿌린 상어 번호를 기억해야 한다.
상어를 이동시킬 곳을 찾아야 한다.
- 냄새가 없는 곳이 가장 높은 우선순위 를 띈다.
- 냄새가 없는 곳이 없다. 즉, 모든 방향이 냄새로 가득 찼다면, 방향 우선순위에 따라 내 냄새가 처음 발견되는 곳 으로 이동시켜야 한다.
모든 상어를 동시에 이동시켜야 한다.

static class Smell {
    int sharkIdx, x, y, smellCnt;

    public Smell(int sharkIdx, int x, int y, int smellCnt) {
        this.sharkIdx = sharkIdx;
        this.x = x;
        this.y = y;
        this.smellCnt = smellCnt;
    }
}

Smell 클래스 는 상어 번호와 좌표 및 냄새가 사라지는데 걸리는 시간을 저장합니다.

static class Shark {
    int idx;
    int x, y, d;
    int nx, ny, nd;
    int[][] priority = new int[5][4];

    public Shark(int idx, int x, int y) {
        this.idx = idx;
        this.x = x;
        this.y = y;
    }

    public Shark(int idx, int x, int y, int nx, int ny, int nd) {
        this.idx = idx;
        this.x = x;
        this.y = y;
        this.nx = nx;
        this.ny = ny;
        this.nd = nd;
    }
}

Shark 클래스 는 상어가 가지고 있어야 할 모든 정보를 저장합니다.

idx 는 상어 번호를, x와 y 는 현재 상어 위치를, d는 현재 상어가 바라보는 방향을 의미합니다.
nx와 ny 는 상어가 다음에 이동할 좌표를, nd 는 상어가 다음에 바라볼 방향을 의미합니다.
배열 priority 는 상어의 상하좌우 방향에 따른 우선순위를 저장합니다.

static void findNextPos() {
    Queue<Shark> moveCandidates = new LinkedList<>();

    for (Shark shark : sharks) {
        if (shark == null) continue;

        int idx = shark.idx, x = shark.x, y = shark.y, d = shark.d;
        int px = 0, py = 0, pd = 0;

        boolean empty = false;
        boolean sameSmell = false;

        for (int dd = 0; dd < 4; dd++) {
            int nd = shark.priority[d][dd];
            int nx = x + dx[nd], ny = y + dy[nd];

            if (!isInRange(nx, ny)) continue;

            if (smellMap[nx][ny] == null) {
                moveCandidates.add(new Shark(idx, x, y, nx, ny, nd));
                empty = true;
                break;
            } else if (!sameSmell && smellMap[nx][ny].sharkIdx == idx) {
                px = nx;
                py = ny;
                pd = nd;
                sameSmell = true;
            }
        }

        if (!empty) {
            moveCandidates.add(new Shark(idx, x, y, px, py, pd));
        }
    }

    decreaseSmell();

    while (!moveCandidates.isEmpty()) {
        Shark shark = moveCandidates.poll();
        moveShark(shark);
    }
}

findNextPos 메소드 는 다음 작업을 수행합니다.

각 상어가 이동하여 위치하게 되는 다음 좌표를 찾아 큐에 저장해놓습니다.
decreaseSmell 메소드 를 호출해 냄새가 사라지는데 걸리는 시간을 1 감소시킵니다.
각 상어의 다음 좌표가 저장되어 있는 큐를 통해, 모든 상어들을 한 번에 이동시킵니다.

위의 for 문에서는 다음에 위치할 좌표를 찾습니다.

제일 처음 마주하는 내 냄새가 적힌 곳의 좌표는 px, py 에, 바라보는 방향은 pd 에 저장해둡니다.
빈 곳에 대한 우선순위가 제일 높으므로, 빈 곳( null ) 을 찾았다면 그 좌표와 바라보는 방향으로 객체를 만든 뒤 큐에 넣어주고 끝냅니다.
빈 곳을 못찾았다면, 이전에 저장해 둔 내 냄새가 있는 곳의 좌표와 방향으로 객체를 만든 뒤 큐에 넣어줍니다.

static void moveShark(Shark shark) {
    int idx = shark.idx, x = shark.x, y = shark.y, nx = shark.nx, ny = shark.ny, nd = shark.nd;
    sharkMap[x][y] = 0;

    if (sharkMap[nx][ny] > 0) {
        int alive = Math.min(sharkMap[nx][ny], idx);
        int dead = Math.max(sharkMap[nx][ny], idx);

        remainedSharksCnt--;

        sharkMap[nx][ny] = alive;

        sharks[dead] = null;

        if (alive == idx) {
            sharks[alive].x = nx;
            sharks[alive].y = ny;
            sharks[alive].d = nd;
        }
    } else {
        sharkMap[nx][ny] = idx;

        sharks[idx].x = nx;
        sharks[idx].y = ny;
        sharks[idx].d = nd;
    }

    smellMap[nx][ny] = new Smell(alive, nx, ny, k);
}

moveShark 메소드 는 파라미터로 받은 shark 상어를 이동시키는 작업을 수행합니다.

이동할 방향에 다른 상어가 없다면, 상어 정보를 갱신해줍니다.
이동할 방향에 이미 다른 상어가 있다면, 죽일 상어와 살릴 상어를 구분합니다. 먼저 죽는 상어를 처리한 뒤, 살릴 상어가 입력으로 받은 shark 라면, 상어 정보를 갱신해줍니다.
새로 이동됐기에, 냄새를 뿌려줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, k;
    static int[][] sharkMap;
    static Smell[][] smellMap;
    static Shark[] sharks;
    static int[] dx = {0, -1, 1, 0, 0}, dy = {0, 0, 0, -1, 1};
    static int remainedSharksCnt = 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());
        sharkMap = new int[N][N];
        smellMap = new Smell[N][N];
        sharks = new Shark[M + 1];
        remainedSharksCnt = M;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                sharkMap[i][j] = Integer.parseInt(st.nextToken());

                if (sharkMap[i][j] != 0) {
                    sharks[sharkMap[i][j]] = new Shark(sharkMap[i][j], i, j);
                    smellMap[i][j] = new Smell(sharkMap[i][j], i, j, k);
                }
            }
        }

        st = new StringTokenizer(br.readLine());

        for (int sharkIdx = 1; sharkIdx <= M; sharkIdx++) {
            sharks[sharkIdx].d = Integer.parseInt(st.nextToken());
        }

        for (int sharkIdx = 1; sharkIdx <= M; sharkIdx++) {
            for (int dir = 1; dir <= 4; dir++) {
                sharks[sharkIdx].priority[dir] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }
        }

        start();
    }

    static void start() {
        int time = 0;

        while (true) {
            time++;
            findNextPos();
            test(time);

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

    static void findNextPos() {
        Queue<Shark> moveCandidates = new LinkedList<>();

        for (Shark shark : sharks) {
            if (shark == null) continue;

            int idx = shark.idx, x = shark.x, y = shark.y, d = shark.d;
            int px = 0, py = 0, pd = 0;

            boolean empty = false;
            boolean sameSmell = false;

            for (int dd = 0; dd < 4; dd++) {
                int nd = shark.priority[d][dd];
                int nx = x + dx[nd], ny = y + dy[nd];

                if (!isInRange(nx, ny)) continue;

                if (smellMap[nx][ny] == null) {
                    moveCandidates.add(new Shark(idx, x, y, nx, ny, nd));
                    empty = true;
                    break;
                } else if (!sameSmell && smellMap[nx][ny].sharkIdx == idx) {
                    px = nx;
                    py = ny;
                    pd = nd;
                    sameSmell = true;
                }
            }

            if (!empty) {
                moveCandidates.add(new Shark(idx, x, y, px, py, pd));
            }
        }

        decreaseSmell();

        while (!moveCandidates.isEmpty()) {
            Shark shark = moveCandidates.poll();
            moveShark(shark);
        }
    }

    static void moveShark(Shark shark) {
        int idx = shark.idx, x = shark.x, y = shark.y, nx = shark.nx, ny = shark.ny, nd = shark.nd;
        sharkMap[x][y] = 0;

        if (sharkMap[nx][ny] > 0) {
            int alive = Math.min(sharkMap[nx][ny], idx);
            int dead = Math.max(sharkMap[nx][ny], idx);

            remainedSharksCnt--;

            sharkMap[nx][ny] = alive;

            sharks[dead] = null;

            if (alive == idx) {
                sharks[alive].x = nx;
                sharks[alive].y = ny;
                sharks[alive].d = nd;
            }

            smellMap[nx][ny] = new Smell(alive, nx, ny, k);
        } else {
            sharkMap[nx][ny] = idx;

            sharks[idx].x = nx;
            sharks[idx].y = ny;
            sharks[idx].d = nd;

            smellMap[nx][ny] = new Smell(idx, nx, ny, k);
        }
    }

    static void decreaseSmell() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (smellMap[i][j] == null) continue;

                if (--smellMap[i][j].smellCnt == 0) {
                    smellMap[i][j] = null;
                }
            }
        }
    }

    static void test(int time) {
        if (remainedSharksCnt == 1 && sharks[1] != null) {
            System.out.println(time);
            System.exit(0);
        }
    }

    static boolean isInRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

    static class Smell {
        int sharkIdx, x, y, smellCnt;

        public Smell(int sharkIdx, int x, int y, int smellCnt) {
            this.sharkIdx = sharkIdx;
            this.x = x;
            this.y = y;
            this.smellCnt = smellCnt;
        }
    }

    static class Shark {
        int idx;
        int x, y, d;
        int nx, ny, nd;
        int[][] priority = new int[5][4];

        public Shark(int idx, int x, int y) {
            this.idx = idx;
            this.x = x;
            this.y = y;
        }

        public Shark(int idx, int x, int y, int nx, int ny, int nd) {
            this.idx = idx;
            this.x = x;
            this.y = y;
            this.nx = nx;
            this.ny = ny;
            this.nd = nd;
        }
    }
}

Twitter Facebook LinkedIn

김무성

[백준] 19237. 어른 상어

문제 링크

풀이 과정

코드

공유하기

댓글남기기

참고

[프로그래머스] 67256. 키패드 누르기

[프로그래머스] 72410. 신규 아이디 추천

[프로그래머스] 81301. 숫자 문자열과 영단어

[JavaScript] 문자열을 정수로 변환하는 세 가지 방법