• Feed
  • Explore
  • Ranking
/
/
    Problem Solving

    [Baekjoon] 마법사 상어와 복제

    마법사 상어와 복제_23290 [골드 1]
    ImplementationSimulation백준
    h
    hyeonZIP
    2026.02.25
    ·
    7 min read

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

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

public class Main {
    private static final int NOT_USAGE = 0;
    private static final int[] dy = new int[]{NOT_USAGE, 0, -1, -1, -1, 0, 1, 1, 1};
    private static final int[] dx = new int[]{NOT_USAGE, -1, -1, 0, 1, 1, 1, 0, -1};

    private static final int[] sy = new int[]{NOT_USAGE, -1, 0, 1, 0};// 상 좌 하 우
    private static final int[] sx = new int[]{NOT_USAGE, 0, -1, 0, 1};// 1 2 3 4

    private static class Fish {

        List<Integer> fish;

        public Fish(List<Integer> fish) {
            this.fish = fish;
        }

        public void addFish(int direction) {
            this.fish.add(direction);
        }

        public void addAllFish(List<Integer> fish) {
            this.fish.addAll(fish);
        }

        public Fish copy() {
            return new Fish(List.copyOf(this.fish));
        }

        public boolean isExistingFish() {
            return !this.fish.isEmpty();
        }

        public int getFishCount() {
            return this.fish.size();
        }

        public void removeFish() {
            this.fish = new ArrayList<>();
        }
    }

    private static class Shark {

        int y, x, point, moveCount, path;
        boolean[][] visited;

        public Shark(int y, int x, int point, int moveCount, int path, boolean[][] visited) {
            this.y = y;
            this.x = x;
            this.point = point;
            this.moveCount = moveCount;
            this.path = path;
            this.visited = visited;
        }
    }

    private static int answer;
    private static int S;
    private static int sharkY;
    private static int sharkX;
    private static Fish[][] fishMap;
    private static int[][] smell;

    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }

    private static void sol() {
        while (S-- > 0) {
            Fish[][] copiedFishMap = copyFish();

            moveFish();

            moveShark();

            removeSmell();

            applyCopiedFish(copiedFishMap);
        }
        calculateAllFish();
    }

    private static Fish[][] copyFish() {
        Fish[][] copiedFishMap = initFishMap();

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                copiedFishMap[i][j] = fishMap[i][j].copy();
            }
        }

        return copiedFishMap;
    }

    private static void moveFish() {
        Fish[][] newFishMap = initFishMap();

        for (int y = 1; y <= 4; y++) {
            for (int x = 1; x <= 4; x++) {
                if (fishMap[y][x].isExistingFish()) {
                    List<Integer> fishDirections = fishMap[y][x].fish;

                    for (int direction : fishDirections) {
                        boolean canMove = false;
                        int ny = -1;
                        int nx = -1;
                        int nd = direction;
                        for (int i = 0; i < 8; i++) {
                            ny = y + dy[nd];
                            nx = x + dx[nd];

                            if (isOutOfRange(ny, nx) || isSharkPlaced(ny, nx) || isFishSmell(ny,
                                nx)) {
                                nd = nd - 1 > 0 ? nd - 1 : 8;
                            } else {
                                canMove = true;
                                break;
                            }
                        }

                        if (canMove) {
                            newFishMap[ny][nx].addFish(nd);
                        } else {
                            newFishMap[y][x].addFish(direction);
                        }
                    }
                }
            }
        }

        fishMap = newFishMap;
    }

    private static void moveShark() {
        Deque<Shark> stack = new ArrayDeque<>();
        stack.push(new Shark(sharkY, sharkX, 0, 0, 0, new boolean[5][5]));

        int finalPath = 0;
        int maximumPoint = 0;

        while (!stack.isEmpty()) {
            Shark s = stack.pop();

            int y = s.y;
            int x = s.x;
            int point = s.point;
            int moveCount = s.moveCount;
            int path = s.path;
            boolean[][] visited = s.visited;

            if (moveCount == 3) {
                if (maximumPoint <= point) {
                    maximumPoint = point;
                    finalPath = path;
                }

                continue;
            }

            for (int direction = 1; direction <= 4; direction++) {
                int ny = y + sy[direction];
                int nx = x + sx[direction];

                if (isOutOfRange(ny, nx)) {
                    continue;
                }

                boolean[][] nextVisited = new boolean[5][5];
                for (int i = 1; i <= 4; i++) {
                    nextVisited[i] = visited[i].clone();
                }

                int nextPoint = point;
                if (!nextVisited[ny][nx]) {
                    nextPoint += fishMap[ny][nx].getFishCount();
                    nextVisited[ny][nx] = true;
                }
                int nextMoveCount = moveCount + 1;
                int nextPath = path * 10 + direction;

                stack.push(new Shark(ny, nx, nextPoint, nextMoveCount, nextPath, nextVisited));
            }
        } // while

        int[] sharkDirections = Arrays.stream(String.valueOf(finalPath).split(""))
            .mapToInt(Integer::parseInt)
            .toArray();

        for (int direction : sharkDirections) {
            sharkY += sy[direction];
            sharkX += sx[direction];

            if (fishMap[sharkY][sharkX].isExistingFish()) {
                smell[sharkY][sharkX] = 3;
                fishMap[sharkY][sharkX].removeFish();
            }
        }
    }

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

    private static void applyCopiedFish(Fish[][] copiedFishMap) {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                fishMap[i][j].addAllFish(copiedFishMap[i][j].fish);
            }
        }
    }

    private static void calculateAllFish() {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                answer += fishMap[i][j].fish.size();
            }
        }
    }

    private static boolean isOutOfRange(int y, int x) {
        return y < 1 || x < 1 || y > 4 || x > 4;
    }

    private static boolean isSharkPlaced(int y, int x) {
        return y == sharkY && x == sharkX;
    }

    private static boolean isFishSmell(int y, int x) {
        return smell[y][x] > 0;
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int m = Integer.parseInt(st.nextToken());// 물고기 수
        S = Integer.parseInt(st.nextToken());// 마법 연습 횟수

        fishMap = initFishMap();
        smell = new int[5][5];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            fishMap[y][x].addFish(d);
        }

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

        sharkY = Integer.parseInt(st.nextToken());
        sharkX = Integer.parseInt(st.nextToken());

    }

    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }

    private static Fish[][] initFishMap() {
        Fish[][] fishMap = new Fish[5][5];

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                fishMap[i][j] = new Fish(new ArrayList<>());
            }
        }

        return fishMap;
    }
}

    주요 개념

    • 구현

    • 시뮬레이션

    풀이 방법

    • 구현, 시뮬레이션 문제는 효율적인 자료형을 빠르게 구하는 것이 핵심이다.

    • 각 격자에 물고기들의 방향을 저장하는 2차원 배열 Fish

      • 내부 필드는 물고기들의 방향만 List로 담아 하나의 격자에 여러 물고기가 들어가 있을 수 있도록 한다.

    • 상어의 좌표는 별도의 변수 2개로 표현한다.

    • 물고기를 먹고 남은 냄새 표현을 위한 2차원 배열 smell

    • 배열의 크기가 4*4 이고 메모리 제한도 널널한 만큼 구현 방법은 무궁무진하다.

    • 주의할 점은 상어가 움직이는 경로 우선순위를 정할 때, 물고기를 먹는 점수 체크와 사전 순이다.

      • 방문 체크로 중복되는 물고기일 경우 점수에 포함시키지 않는다.

      • Stack의 성질을 활용하여 444 부터 111까지 탐색하도록 하여 최댓값과 동일하거나 큰 경우를 조건으로 걸어 자연스럽게 사전순을 충족시켰다.

    - 컬렉션 아티클