백준 21611번: 마법사 상어와 블리자드 (Java)

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

21611번: 마법사 상어와 블리자드

 

 

 

 

 

 

 

 

---

 

풀이

길이 구부정하게 있으므로 큐로 구현하면 각 method 구현이 간단합니다(머리를 싸매지 않아도 됩니다.). 다만, 속도도 빠를 줄 알았는데 그렇진 않네요. 다른 코드를 보니, 1차원 배열로 구현한게 더 빠릅니다.

제 풀이가 꽤 유니크한 편일 겁니다..ㅎㅎ

 

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[] dr = { 0, -1, 1, 0, 0 };
    static int[] dc = { 0, 0, 0, -1, 1 };
    static int[][] map;
    static int N;
    static Queue<Integer> pebbles = new ArrayDeque<>();
    static int ans = 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());
        int M = Integer.parseInt(st.nextToken());
        map = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        init();
        int x = 0;
        while (x++ < M)    {
            st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            blizzard(d, s);
            while (true) {
                if (!pop()) break;
            }
            copy();
        }
        System.out.println(ans);
    }
    
    static void init() {
        for (int i = 1; i < N*N; i++) {
            int[] cur = loc(i);
            int r = cur[0], c = cur[1];
            if (map[r][c] == 0) continue;
            pebbles.offer(map[r][c]);
        }
    }
    
    static void blizzard(int d, int s) {
        Set<Integer> destroy = new HashSet<>();
        int mid = (N+1)/2;
        int r = mid, c = mid;
        for (int i = 0; i < s; i++) {
            r += dr[d];
            c += dc[d];
            destroy.add(idx(r, c));
        }
        
        Queue<Integer> nextPebbles = new ArrayDeque<>();
        int idx = 1;
        while (!pebbles.isEmpty()) {
            if (destroy.contains(idx)) pebbles.poll();
            else nextPebbles.offer(pebbles.poll());
            idx++;
        }
        pebbles = nextPebbles;
    }
    
    static boolean pop() {
        boolean flag = false;
        Queue<Integer> tempPebbles = new ArrayDeque<>();
        Queue<Integer> nextPebbles = new ArrayDeque<>();
        while (!pebbles.isEmpty()) {
            if (tempPebbles.isEmpty()) tempPebbles.offer(pebbles.poll());
            else {
                if (tempPebbles.peek() == pebbles.peek()) {
                    tempPebbles.offer(pebbles.poll());
                } else {
                    if (tempPebbles.size() < 4) {
                        while (!tempPebbles.isEmpty()) {
                            nextPebbles.offer(tempPebbles.poll());
                        }
                        tempPebbles.offer(pebbles.poll());
                    } else {
                        ans += tempPebbles.peek() * tempPebbles.size();
                        tempPebbles.clear();
                        tempPebbles.offer(pebbles.poll());
                        flag = true;
                    }
                }
            }
        }
        if (tempPebbles.size() < 4) {
            while (!tempPebbles.isEmpty()) {
                nextPebbles.offer(tempPebbles.poll());
            }
        } else {
            ans += tempPebbles.peek() * tempPebbles.size();
            tempPebbles.clear();
            flag = true;
        }
        pebbles = nextPebbles;
        return flag;
    }
    
    static void copy() {
        Queue<Integer> tempPebbles = new ArrayDeque<>();
        Queue<Integer> nextPebbles = new ArrayDeque<>();
        while (!pebbles.isEmpty()) {
            if (tempPebbles.isEmpty()) tempPebbles.offer(pebbles.poll());
            else {
                if (tempPebbles.peek() == pebbles.peek()) {
                    tempPebbles.offer(pebbles.poll());
                } else {
                    nextPebbles.offer(tempPebbles.size());
                    nextPebbles.offer(tempPebbles.peek());
                    tempPebbles.clear();
                    tempPebbles.offer(pebbles.poll());
                }
            }
        }
        
        if (!tempPebbles.isEmpty()) {
            nextPebbles.offer(tempPebbles.size());
            nextPebbles.offer(tempPebbles.peek());
            tempPebbles.clear();
        }
        
        int cnt = 0;
        while (!nextPebbles.isEmpty() && cnt < N*N-1) {
            pebbles.offer(nextPebbles.poll());
            cnt++;
        }
        nextPebbles.clear();
    }
    
    // (r, c)의 위치를 찾는 method
    static int idx(int r, int c) {
        int m = (N+1)/2;
        int l = Math.max(Math.abs(r-m), Math.abs(c-m));
        int ret = (2*l-1)*(2*l-1) - 1;
        if (c == m-l && r > m-l) ret += r - (m-l);
        else if (r == m+l) ret += 2*l + c - (m-l);
        else if (c == m+l) ret += 4*l + (m+l) - r;
        else ret += 6*l + (m+l) - c;
        return ret;
    }
    
    // i번째 구슬의 위치를 찾는 method
    static int[] loc(int idx) {
        int m = (N+1)/2;
        int l = (int) (Math.sqrt(idx)+1) / 2;
        idx -= (2*l-1)*(2*l-1) -1;
        if (idx <= 2*l) return new int[] {m-l+idx, m-l};
        else if (idx <= 4*l) return new int[] {m+l, (idx-2*l) + (m-l)};
        else if (idx <= 6*l) return new int[] {(m+l)-(idx-4*l), m+l};
        else return new int[] {m-l, (m+l) - (idx-6*l)};
    }
}