백준 23290번: 마법사 상어와 복제 (Java)

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

23290번: 마법사 상어와 복제

 

 

 

 

 

 

 

 

---

 

풀이

1. 물고기를 저장하는 방법이 제일 중요해 보입니다.

1) 물고기를 배열에 저장할 경우

 - 물고기의 수를 F라 한다면, 대략 O(FS)입니다. 문제 조건에서 '격자 위의 물고기 수는 항상 백만 이하인 조건만 들어온다'를 믿고 F <= 1,000,000라 가정하여 '되겠지~'하고 풀었는데 사실 시간 초과가 떠도 이상하진 않습니다.

2) 물고기를 3차원 배열에 저정하는 경우

 - fish[i][j][k]를 (i, j)에 방향이 k인 물고기 수로 저장을 하면, 대략 l*(64*3*8 + k*16*8) * S (= O(S)이긴 한데 Big-O로 표현하기 애매하니...) 번의 단위 연산을 수행합니다. k, l은 적당한 상수이며, 64*3*8은 상어의 움직임을 찾는 경우, 16*8은 물고기 배열 for문 도는 경우를 의미합니다. 이 방법은 물고기 수와 상관없이 일정한 수행 시간을 보장합니다. 실제로 2) 풀이가 훨씬 빠릅니다.

 

 

2. 나머지 구현

1) 물고기 복사: 그냥 배열을 복사했다가, 마지막에 값을 더해주면 됩니다.

2) 물고기 이동: 적당히 해줍니다.

3) 상어 이동: 최대 64가지의 가능한 이동 중, 이동에서의 최댓값을 정의하여 최댓값 이동을 수행합니다.

4) 냄새: 2턴 이후 없어지므로, 3)을 하는 도중 상어가 먹었다면 냄새를 3으로 초기화하여, 매 수행마다 1씩 감소시키면 됩니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] dr1 = { 0, -1, -1, -1, 0, 1, 1, 1 }; // 0-based: 계산 편의
    static int[] dc1 = { -1, -1, 0, 1, 1, 1, 0, -1 };
    static int[] dr2 = { 0, -1, 0, 1, 0 }; // 1-based
    static int[] dc2 = { 0, 0, -1, 0, 1 };
    static int[][] smell = new int[5][5];
    static int[][][] fishs = new int[5][5][8];
    static int[][][] tempFishs;
    static int sharkR, sharkC;
    static Move maxMove; // 상어가 최대로 많이 먹으면서 사전순으로 앞서는 움직임 저장
    static int[][] sharkVisited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int dir = Integer.parseInt(st.nextToken())-1; // 계산 편의
            fishs[x][y][dir]++;
        }
        
        st = new StringTokenizer(br.readLine());
        sharkR = Integer.parseInt(st.nextToken());
        sharkC = Integer.parseInt(st.nextToken());
        
        while (S-- > 0) {
            initMagic();
            moveFish();
            moveShark();
            smellReduce();
            completeMagic();
        }
        System.out.println(count());
    }
    
    // 마법사 상어가 복사를 하는 method
    static void initMagic() {
        tempFishs = new int[5][5][8];
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 0; k < 8; k++) {
                    tempFishs[i][j][k] = fishs[i][j][k];
                }
            }
        }
    }
    
    // 물고기들이 움직이는 걸 수행하는 method
    static void moveFish() {
        int[][][] nextFish = new int[5][5][8];
        
        for (int i = 1; i <= 4; i++) {
             for (int j = 1; j <= 4; j++) {
                 for (int k = 0; k < 8; k++) {
                     boolean flag = false;
                     // 움직일 수 있는 방향을 반시계 방향으로 돌리면서 찾기
                     for (int x = 0; x < 8; x++) {
                         int dir = (k+7*x)%8;
                         int nr = i + dr1[dir], nc = j + dc1[dir];
                         if (!isIn(nr, nc)) continue;
                         if ((sharkR == nr && sharkC == nc) || smell[nr][nc] > 0) continue;
                         nextFish[nr][nc][dir] += fishs[i][j][k];
                         flag = true;
                         break;
                     }
                     // 움직이지 못했다면 제자리
                     if (!flag)    nextFish[i][j][k] += fishs[i][j][k];
                 }
             }
        }
        fishs = nextFish;
    }
    
    // 상어가 움직이면서 물고기를 먹고, 먹은 자리에 냄새를 남기는 method
    static void moveShark() {
        sharkVisited = new int[5][5];
        maxMove = new Move(0, "999");
        // 최적의 움직임을 구하기
        findMaxMove(0, 0, sharkR, sharkC, "");
        for (int i = 0; i < 3; i++) {
            int dir = maxMove.move.charAt(i) - '0';
            sharkR += dr2[dir];
            sharkC += dc2[dir];
            int f = 0;
            for (int k = 0; k < 8; k++) {
                f += fishs[sharkR][sharkC][k];
                fishs[sharkR][sharkC][k] = 0;
            }
            if (f > 0) {
                smell[sharkR][sharkC] = 3;
            }
        }
    }
    
    // 가장 많은 물고기를 먹고, 사전순으로 가장 앞서는 움직임을 찾는 method
    static void findMaxMove(int cnt, int eat, int r, int c, String move) {
        if (cnt == 3) {
            Move tempMove = new Move(eat, move);
            if (maxMove.compareTo(tempMove) < 0) {
                maxMove = tempMove;
            }
            return;
        }
        
        for (int i = 1; i <= 4; i++) {
            int nr = r + dr2[i], nc = c + dc2[i];
            if (!isIn(nr, nc)) continue;
            // 이미 방문한 곳을 또 방문 가능: 이 경우에는 중복하여 먹지 않도록
            int curFish = 0;
            if (sharkVisited[nr][nc] == 0) {
                for (int k = 0; k < 8; k++) {
                    curFish += fishs[nr][nc][k];
                }
            }
            sharkVisited[nr][nc]++;
            findMaxMove(cnt+1, eat + curFish, nr, nc, move+i);
            sharkVisited[nr][nc]--;
        }
    }
    
    // 냄새가 사라지는 걸 구현한 method
    static void smellReduce() {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if (smell[i][j] > 0) smell[i][j]--;
            }
        }
    }
    
    // 복사를 완료하는 method
    static void completeMagic() {
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 0; k < 8; k++) {
                    fishs[i][j][k] += tempFishs[i][j][k];
                }
            }
        }
    }
    
    // 물고기 수를 세는 method
    static int count() {
        int ret = 0;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                for (int k = 0; k < 8; k++) {
                    ret += fishs[i][j][k];
                }
            }
        }
        return ret;
    }
 
    // 움직임 class
    static class Move implements Comparable<Move>{
        int eat;
        String move;
        
        public Move(int eat, String move) {
            this.eat = eat;
            this.move = move;
        }
 
        public int compareTo(Move o) {
            if (this.eat == o.eat) {
                return - this.move.compareTo(o.move); // 작은 순서가 크게 -> 최댓값 찾기
            }
            return this.eat - o.eat;
        }
    }
    
    static boolean isIn(int r, int c) {
        return !(r < 1 || r > 4 || c < 1 || c > 4);
    }
}