이번에 풀어본 문제는
백준 21611번 마법사 상어와 블리자드 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Num
{
    int x,y,dir;

    public Num(int x, int y, int dir)
    {
        this.x = x;
        this.y = y;
        this.dir = dir;
    }
    public Num(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N,M;
    static int max_cnt;
    static int [][] getNum;
    static int [] destroyed;
    static Num shark;
    static int [][] map;
    static List<Integer> list;
    static int [] dx = {0,1,0,-1};
    static int [] dy = {-1,0,1,0};
    static int [] shark_x = {-1,1,0,0};
    static int [] shark_y = {0,0,-1,1};
    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());
        M = Integer.parseInt(st.nextToken());

        int center = N / 2;
        max_cnt = N * N;
        list = new LinkedList<>();
        list.add(0); // 상어
        map = new int[N][N];
        getNum = new int[N][N];
        shark = new Num(center,center,0);
        destroyed = new int[4];

        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; ++j) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        setPoints();
        for(int i = 0 ; i < M; ++i)
        {
            st = new StringTokenizer(br.readLine());
            int dir = Integer.parseInt(st.nextToken())-1;
            int dist = Integer.parseInt(st.nextToken());

            blizzard(dir,dist);
            destroy();
            if(list.isEmpty()) break;
            setList();
        }

        int answer = 0;
        for(int i = 1; i < 4; ++i) answer += destroyed[i] * i;
        System.out.print(answer);
    }
    static void setList()
    {
        Queue<Integer> q = new LinkedList<>();
        q.add(0); // 상어
        int add_cnt = 1;
        int size = list.size();
        int pre = list.get(1);
        int cnt = 1;
        for(int i = 2; i < size; ++i)
        {
            int now = list.get(i);
            if(pre == now) cnt++;
            else
            {
                q.add(cnt);
                q.add(pre);
                cnt = 1;
                add_cnt += 2;
                if(add_cnt >= max_cnt) break;
            }
            pre = now;
        }
        if(cnt > 1)
        {
            q.add(cnt);
            q.add(pre);
        }
        list = new LinkedList<>();
        list.addAll(q);
    }
    static void destroy()
    {
        int size = list.size();
        PriorityQueue<Num> remove_q = new PriorityQueue<>(new Comparator<Num>() {
            @Override
            public int compare(Num o1, Num o2) {
                return o2.x - o1.x;
            }
        });
        int cnt = 1;
        for(int i = 1; i < size-1; ++i)
        {
            if(list.get(i) == list.get(i+1)) cnt++;
            else
            {
                if(cnt > 3) remove_q.add(new Num(i-cnt+1,cnt));
                cnt = 1;
            }
        }
        if(!remove_q.isEmpty())
        {
            while(!remove_q.isEmpty())
            {
                Num cur = remove_q.poll();
                int idx = cur.x;
                int num = list.get(idx);
                int t = cur.y;
                destroyed[num] += t;
                for(int i = 0; i < t; ++i) list.remove(idx);
            }
            destroy();
        }
    }
    static void blizzard(int dir, int dist)
    {
        int nx = shark.x;
        int ny = shark.y;
        int rmv_cnt = 0;
        int list_size = list.size();
        for(int i = 0; i < dist; ++i)
        {
            nx += shark_x[dir];
            ny += shark_y[dir];
            if(isValid(nx,ny))
            {
                int val = getNum[nx][ny];
                int rmv_idx = val - rmv_cnt;
                if(rmv_idx < list_size)
                {
                    list.remove(rmv_idx);
                    rmv_cnt++;
                    list_size--;
                }
            }
        }
    }
    static void setPoints()
    {
        int tmp_dist = 0;
        int tmp_x = shark.x;
        int tmp_y = shark.y;
        int tmp_dir = shark.dir;
        int p_idx = 1;
        for (int i = 1; i < N; ++i) {
            tmp_dist++;
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < tmp_dist; ++k) {
                    tmp_x += dx[tmp_dir];
                    tmp_y += dy[tmp_dir];
                    getNum[tmp_x][tmp_y] = p_idx++;
                    if(map[tmp_x][tmp_y] > 0) list.add(map[tmp_x][tmp_y]);
                }
                tmp_dir = (tmp_dir + 1) % 4;
            }
        }
        for (int i = 0; i < tmp_dist; ++i) // 마지막줄
        {
            tmp_x += dx[tmp_dir];
            tmp_y += dy[tmp_dir];
            getNum[tmp_x][tmp_y] = p_idx++;
            if(map[tmp_x][tmp_y] > 0) list.add(map[tmp_x][tmp_y]);
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

📝 풀이

상당히 복잡한 구현문제입니다.
2차원 배열에 표현되어 있지만 달팽이 모양처럼 일자로 연결된 연속된 번호를 가진 칸이 존재하며, 리스트로 구현해 보았습니다. 1부터 N제곱까지 존재하는 각 번호에 해당되는 좌표를 setPoints함수를 한번 수행하여 담아주고, 블리자드를 사용할 때, 해당 번호에 맞는 좌표의 값을 통해 구슬이 지워질 수 있도록 합니다. 0이 아닌 값이라면 리스트에도 값을 담아주며, 리스트는 현재 존재하는 구슬들의 번호를 지니고 있습니다. 초기값을 모두 담았다면 list내의 구슬들의 연속되는 숫자를 찾아 4개 이상일 경우 폭발시키며, 각 구슬 번호에 따라 득점값이 다르기 때문에 구슬의 번호를 인덱스로 갖는 destroyed 배열에 폭발된 개수를 누적하여 더해주어, 마지막에 결과를 계산할 수 있도록 했습니다. 마지막으로, 폭발이 끝난 후에는 조건에 맞게 구슬이 분산되고, 이 과정을 M번 반복하는 문제입니다.

📜 후기

최근 풀었던 문제 중 가장 어려웠던 것 같습니다. 사실 이 코드를 제출하면 시간초과가 나는데, 중간에 코딩테스트가 겹쳐서 붕 뜨긴 했지만 이틀정도 투자해보았으나 어느 부분에서 시간을 단축해야할지 감이 오지 않아 우선 기록하고자 현재 상태로 업로드 하게 되었습니다. 배열을 달팽이 모양으로 탐색하며 각 번호에 대한 좌표값을 얻는 과정은 불가피하다고 생각되는데, 이 부분이나 구슬을 파괴하는 destroy함수에서 시간을 조금 많이 뺏기지 않나 싶습니다..
destroy 함수를 가장 많이 수정했었는데, 처음에는 입력값이 이렇게 큰지 몰랐어서 정규식을 사용했다가 당연히 실패했고, list를 범위로 삭제하기 위해 sublist도 사용해보았으나, 속도가 remove에 비해 느리길래 결국 remove를 사용하게 됐습니다. 그런데도 해결이 되지 않아 조금 당황스럽긴 한데... 좀 더 공부해보고 다음에 처음부터 다시 풀어볼 생각입니다!