백준 23291번: 어항 정리 (Java)

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

23291번: 어항 정리

 

 

 

 

 

 

 

 

---

풀이

 

한 번에 시행동안

1) 가장 적은 물고기를 가지고 있는 어항에 물고기 넣어주기 - putFish()

2) 첫 번째 마법 - magic1() 

3) 물고기 수 조절 - spread()

4) 다시 일자로 펴주기 - badak()

5) 두 번째 마법 - magic2()

6) 물고기 수 조절 - spread()

7) 다시 일자로 펴주기 - badak()

8) 최대 물고기 수 어항 - 최소 물고기 수 어항 <= K인지 확인

을 수행하면 됩니다.

 

여기서 magic1()이 제일 어렵고, 나머지는 할 만 합니다.

 

※ 시간 복잡도에 관한 이야기

수행 횟수를 C라 하면, 1) ~ 8) method의 구현을 이차원 배열로 naive하게 했다고 하면 (아마 계수가 꽤 크게 붙는) O(N^2C)가 됩니다. C가 크다면 시간 초과가 우려될만한데, 아마 C는 대략적으로 log(최대 물고기 수 어항)에 비례할 겁니다. 그리고 물고기 수 어항은 최대 10000이므로, 수행 시간이 널널하지 않나 싶습니다.

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static int N, K;
    // temp: 돌린 배열을 임시로 저장, tempFish: 물고기 수 조절할 때 임시로 저장
    static int[][] fishbowl, temp, tempFish;
 
    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());
        K = Integer.parseInt(st.nextToken());
        fishbowl = new int[N+1][N+1];
        tempFish = new int[N+1][N+1];
        st = new StringTokenizer(br.readLine());
        for (int j = 1; j <= N; j++) {
            fishbowl[N][j] = Integer.parseInt(st.nextToken());
        }
        
        int cnt = 0;
        while (true) {
            cnt++;
            putFish(); 
            magic1(); 
            spread();
            badak();
            magic2();
            spread();
            badak();
            if (check()) break;
        }
        System.out.println(cnt);
    }
    
    // 물고기의 수가 가장 적은 위치에 물고기를 넣어주자.
    static void putFish() {
        int min = 10000;
        for (int j = 1; j <= N; j++) {
            if (fishbowl[N][j] > 0 && fishbowl[N][j] < min) {
                min = fishbowl[N][j];
            }
        }
        
        for (int j = 1; j <= N; j++) {
            if (fishbowl[N][j] == min) {
                fishbowl[N][j]++;
            }
        }
    }
 
    static void magic1() {
        int x = N, y = 1, r = 1, c = 1;
        while (true) {
            // 돌리고 맞는 위치에 넣고 기존 위치 물고기 삭제
            temp = rotate(x-r+1, y, r, c);
            put(x-c, y+c, c, r);
            delete(x-r+1, y, r, c);
            
            y += c;
            r++;
            if (y+r+c-1 > N) break;
            
            temp = rotate(x-r+1, y, r, c);
            put(x-c, y+c, c, r);
            delete(x-r+1, y, r, c);
 
            y += c;
            c++;
            if (y+r+c-1 > N) break;
        }
    }
    
    // 물고기 수 조절 후 다시 바닥으로 보내기
    static void badak() {
        int c = 1;
        for (int j = 1; j <= N; j++) {
            if (fishbowl[N-1][j] > 0) {
                for (int i = N; i > 0; i--) {
                    if (fishbowl[i][j] == 0) break;
                    fishbowl[N][c++] = fishbowl[i][j];
                    fishbowl[i][j] = 0;
                }
            }
        }
    }
    
    // 물고기 수 조절하는 method
    static void spread() {
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (fishbowl[r][c] == 0) continue;
                for (int i = 0; i < 4; i++) {
                    int nr = r + dr[i], nc = c + dc[i];
                    if (!isIn(nr, nc) || fishbowl[nr][nc] == 0) continue;
                    if (fishbowl[r][c] <= fishbowl[nr][nc]) continue;
                    int d = (fishbowl[r][c] - fishbowl[nr][nc]) / 5;
                    tempFish[nr][nc] += d;
                    tempFish[r][c] -= d;
                }
            }
        }
        
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (tempFish[r][c] == 0) continue;
                fishbowl[r][c] += tempFish[r][c];
                tempFish[r][c] = 0;
            }
        }
    }
    
    // 두 번째 마법: 180도 돌리는 것보다 직접 구현이 편함
    static void magic2() {
        for (int j = 1; j <= N/2; j++) {
            fishbowl[N-1][N+1-j] = fishbowl[N][j]; 
            fishbowl[N][j] = 0;
        }
        
        for (int i = -1; i <= 0; i++) {
            for (int j = N/2+1; j <= 3*N/4; j++) {
                fishbowl[N-3-i][N+N/2+1-j] = fishbowl[N+i][j];
                fishbowl[N+i][j] = 0;
            }
        }
    }
    
    // 문제 조건에 맞는지 확인
    static boolean check() {
        int max = 1;
        int min = 10000;
        for (int j = 1; j <= N; j++) {
            if (fishbowl[N][j] < min) min = fishbowl[N][j];
            if (fishbowl[N][j] > max) max = fishbowl[N][j];
        }
        return max - min <= K;
    }
    
    // 공중부양 시킬 물고기를 90도 돌리기
    // (x, y)을 왼쪽 위 기준점으로 하여, row 길이가 r, col 길이가 c인 배열을 돌려 [c][r] 배열 return
    static int[][] rotate(int x, int y, int r, int c) {
        int[][] ret = new int[c][r];
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < r; j++) {
                ret[i][j] = fishbowl[x+r-1-j][y+i]; // TODO
            }
        }
        return ret;
    }
    
    // (x, y)을 왼쪽 위 기준점으로 하여, row 길이가 r, col 길이가 c인 배열 넣기
    static void put(int x, int y, int r, int c) {
        for (int i = 0; i < r; i++    ) {
            for (int j = 0; j < c; j++) {
                fishbowl[x+i][y+j] = temp[i][j];
            }
        }
    }
    
    // (x, y)을 왼쪽 위 기준점으로 하여, row 길이가 r, col 길이가 c인 배열 삭제
    static void delete(int x, int y, int r, int c) {
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                fishbowl[x+i][y+j] = 0;
            }
        }
    }
    
    static boolean isIn(int r, int c) {
        return !(r <= 0 || r > N || c <= 0 || c > N);
    }
}