[BOJ19237] 어른 상어 (Java, 구현, 시뮬레이션)

문제 링크

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

 

풀이

개인적으로 상어 시리즈 문제 중에서 쉬운 편이었다고 생각한다

구현 요구사항이 복잡해서 이해하는 수고가 필요할 뿐이지 반복문만으로 풀이 가능하였다 

 

처음에 이해가 어려웠던게 아래의 상어의 방향별 우선순위 표였다

문제에서 1, 2, 3, 4는 각각 위, 아래, 왼쪽, 오른쪽을 의미할 때
①번 상어는 처음 오른쪽 방향을 바라보기 때문에 이동 가능한 위치를 탐색할 때 → ← ↑ ↓ 순으로 "빈칸" 또는 "자기 냄새나는 영역"을 찾는다

출처 - 백준 19237번 어른 상어

 

입출력 예시도 상어의 방향별 우선순위 때문에 처음에 알아보기 쉽지 않았지만, 두번 풀이하니 적응이 된다 

입출력 예시 1에서

5 4 4          // n m k (n : n * n, m : 상어 마리 수, k : 상어 냄새 유효 시간)
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  // 1 ~ m 번 상어별 초기 방향
2 3 1 4  // 1번 상어가 1(위)를 바라볼 때 탐색 우선 순위
4 1 2 3  // 1번 상어가 2(아래)를 바라볼 때 탐색 우선 순위
3 4 2 1  // 1번 상어가 3(왼쪽)을 바라볼 때 탐색 우선 순위
4 3 1 2  // 1번 상어가 4(오른쪽)를 바라볼 때 탐색 우선 순위
// .. 이하 생략

 

 

격자형 필드에서 상어 정보를 2중 for문으로 찾는게 번거로워 Shark(정적 클래스) 배열로 관리하는 방식으로 풀이했다

상어가 이동 가능한 위치가 없거나, 같은 칸에서 경합이 발생했을 때 큰 상어를 sharks[no] = null 처리하는데 이게 적합한지는 잘 모르겠다.
null 검사 조건문이 들어가니 코드 한 줄이 늘고, 안 하자니 NPE 발생할 수 있고 ..더 좋은 방법은 없나 싶다 (?)

private static int[][][] maps;
private static Shark[] sharks;

 

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    // 위, 아래, 왼쪽, 오른쪽
    private static final int[][] DIR = {
            {-1, 0},
            {1, 0},
            {0, -1},
            {0, 1}
    };

    private static int n, m, k;
    private static int[][][] maps;
    private static int[][][] priority;
    private static Shark[] sharks;

    private static void input() {
        n = inputProcessor.nextInt(); // n * n
        m = inputProcessor.nextInt(); // 상어 m 마리
        k = inputProcessor.nextInt(); // 냄새

        sharks = new Shark[m + 1];
        maps = new int[n + 1][n + 1][2]; // 0 : 상어 번호, 1 : 냄새 유효 시간
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                int no = inputProcessor.nextInt();

                if(no == 0) continue;

                maps[i][j][0] = no;
                maps[i][j][1] = k;
                sharks[no] = new Shark(i, j, -1);
            }
        }

        // i 번 상어의 초기 방향
        for(int i = 1; i <= m; i++) {
            sharks[i].d = inputProcessor.nextInt() - 1;
        }

        // 상어별 방향 우선 순위
        priority = new int[m + 1][4][4];
        for(int i = 1; i <= m; i++) { // i번 상어
            for(int j = 0; j < 4; j++) { // 0: 위, 1 : 아래, 2: 왼쪽, 3:오른쪽 일때 우선 순위
                priority[i][j][0] = inputProcessor.nextInt() - 1;
                priority[i][j][1] = inputProcessor.nextInt() - 1;
                priority[i][j][2] = inputProcessor.nextInt() - 1;
                priority[i][j][3] = inputProcessor.nextInt() - 1;
            }
        }
    }

    private static class Shark {
        private final int x;
        private final int y;
        private int d; // 방향

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

    private static void pro() {
        int result = -1;
        for(int t = 1; t <= 1000; t++) {
            // 상어가 이동 가능한 다음 위치를 찾는다 (빈칸, 자기 냄새)
            // 냄새를 지운다 (실수* 냄새를 먼저 지우면 의도치 않은 빈칸이 생겨 결과 틀려짐)
            // 이동 후 냄새를 뿌린다
            findNextPosition();
            updateSmell();
            moveShark();

            // 1번 상어 혼자 살아 남았는가
            if(liveOnlyOne()) {
                result = t;
                break;
            }
        }


        sb.append(result);
    }

    private static void findNextPosition() {
        for(int no = 1; no <= m; no++) {
            if(sharks[no] == null) continue;

            Shark next = move(sharks[no], no);
            sharks[no] = next;
        }
    }

    private static void updateSmell() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(maps[i][j][0] == 0) continue; // 빈 칸

                if(maps[i][j][1] > 0 && --maps[i][j][1] == 0) { // 냄새
                    maps[i][j][0] = 0;
                }
            }
        }
    }

    private static void moveShark() {
        for(int no = 1; no <= m; no++) {
            if(sharks[no] == null) continue;

            int x = sharks[no].x;
            int y = sharks[no].y;

            if(maps[x][y][0] > 0 && maps[x][y][0] < no) { //경합을 할 때 큰 상어가 쫓겨난다
                sharks[no] = null;
                continue;
            }

            maps[x][y][0] = no;
            maps[x][y][1] = k;
        }
    }

    private static Shark move(Shark shark, int no) {
        int x = shark.x;
        int y = shark.y;
        int d = shark.d; // 현재 방향

        // 빈칸이 있는가
        for(int i = 0; i < 4; i++) {
            int prior = priority[no][d][i];
            int dx = x + DIR[prior][0];
            int dy = y + DIR[prior][1];

            if(dx < 1 || dy < 1 || dx > n || dy > n) continue;
            if(maps[dx][dy][0] != 0) continue; // 빈칸이 아니라면

            return new Shark(dx, dy, prior);
        }

        // 자기 냄새가 나는 영역이 있는가
        for(int i = 0; i < 4; i++) {
            int prior = priority[no][d][i];
            int dx = x + DIR[prior][0];
            int dy = y + DIR[prior][1];

            if(dx < 1 || dy < 1 || dx > n || dy > n) continue;
            if(maps[dx][dy][0] != no && maps[dx][dy][1] > 0) continue; // 자기 영역이 아니라면

            return new Shark(dx, dy, prior);
        }

        return null;
    }

    private static boolean liveOnlyOne() {
        for(int i = 2; i <= m; i++) {
            if(sharks[i] != null) return false;
        }

        return true;
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

}