[Baekjoon] 21611: 마법사 상어와 블리자드

문제

상하좌우로 블리자드를 쏴대는 상어 문제이다.

 

예시가 궁금하다면 여기서 확인하자. [Baekjoon] 21611: 마법사 상어와 블리자드

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

 

풀이

내 풀이

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

public class Q21611 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[] startOrder = {7, 3, 1, 5}; // 0: 상, 1: 하, 2: 좌, 3: 우
    private static int[][] moveDirections = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    private static int[] boomCounts = {0, 0, 0};
    private static List<Integer> marbles = new ArrayList<>();
    private static int n, m;
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        input();
        addMarbles();
        if (marbles.size() == 0) {
            System.out.println(0);
            return;
        }

        blizzard();

        System.out.println(boomCounts[0] + (boomCounts[1] * 2) + (boomCounts[2] * 3));
    }

    private static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(row[j]);
            }
        }
    }

    private static void addMarbles() { // 구슬들을 1차원 리스트에 넣는다.
        int straightDistance = 1;
        int straightCount = 0;
        int turnCount = 0;
        int curRow = n / 2;
        int curCol = n / 2;
        int curDirection = 0;
        while (true) {
            curRow += moveDirections[curDirection][0];
            curCol += moveDirections[curDirection][1];
            if (map[curRow][curCol] == 0) {
                break;
            }
            marbles.add(map[curRow][curCol]);

            if (curRow == 0 && curCol == 0) {
                break;
            }

            straightCount++;
            if (straightCount == straightDistance) {
                straightCount = 0;
                curDirection = (curDirection + 1) % 4;
                turnCount++;
                if (turnCount == 2) {
                    turnCount = 0;
                    straightDistance++;
                }
            }
        }
    }

    private static void blizzard() throws IOException {
        for (int i = 0; i < m; i++) {
            String[] blizzard = br.readLine().split(" ");
            int direction = Integer.parseInt(blizzard[0]) - 1;
            int distance = Integer.parseInt(blizzard[1]);
            Deque<Integer> indexes = new ArrayDeque<>();

            int curMarbleCount = marbles.size();
            int count = 2;
            for (int j = 0; j < distance; j++) {
                int index = (4 * count * (count - 1)) - ((8 - startOrder[direction]) * (count - 1)); // 없애는 구슬의 인덱스를 구하기 위한 수식
                if (index > curMarbleCount) {
                    break;
                }
                indexes.offerLast(index - 1); // 인덱스에 넣는다. 왜 why?
                count++;
            }

            while (!indexes.isEmpty()) { // 삭제 연산을 거꾸로 해야 영향이 없기 때문
                int index = indexes.pollLast();
                marbles.remove(index);
            }

            while (boom()) {
            }

            transform();
        }
    }

    public static boolean boom() { // 구슬 폭발: 투 포인터를 사용하여 폭파시킨다.
        boolean boom = false;
        List<Integer> newMarbles = new ArrayList<>();
        int marbleCount = marbles.size();
        int left = 0;
        int right = 0;
        while (right < marbleCount) {
            if (marbles.get(left).equals(marbles.get(right))) { // 왼쪽 포인터와 오른쪽 포인터의 값이 같으면 오른쪽 포인터를 1 증가시킨다.
                right++;
                continue;
            }

            // 포인터의 값이 서로 다르다면
            int num = marbles.get(left);
            if (right - left < 4) { // 오른쪽 포인터와 왼쪽 포인터의 차가 4 미만이라면 왼쪽 포인터가 가리키는 값을 (right-left)만큼 넣어준다.
                for (int i = 0; i < right - left; i++) {
                    newMarbles.add(num);
                }
            } else { // 4 이상이면
                boom = true; // 붐!
                boomCounts[num - 1] += (right - left); // 붐 카운트를 (right-left)만큼 증가시킨다.
            }
            left = right;
        }

        if (left < marbleCount) {
            int num = marbles.get(left);
            if (right - left < 4) {
                for (int i = 0; i < right - left; i++) {
                    newMarbles.add(num);
                }
            } else {
                boom = true;
                boomCounts[num - 1] += (right - left);
            }
        }

        marbles = new ArrayList<>(newMarbles);
        return boom;
    }

    public static void transform() { // 변환
        List<Integer> newMarbles = new ArrayList<>();
        int marbleCount = marbles.size();
        int left = 0; // 폭발과 똑같은 투 포인터 방식으로 했다.
        int right = 0;
        while (right < marbleCount) {
            if (marbles.get(left).equals(marbles.get(right))) { // 같으면 오른쪽 증가
                right++;
                continue;
            }

            // 다르면 (right-left)의 수를 넣고, left가 가리키는 수를 넣는다.
            int num = marbles.get(left);
            newMarbles.add(right - left);
            newMarbles.add(num);
            left = right;
        }

        if (left < marbleCount) {
            int num = marbles.get(left);
            newMarbles.add(right - left);
            newMarbles.add(num);
        }

        marbles = new ArrayList<>(newMarbles.subList(0, Math.min(newMarbles.size(), n * n - 1)));
    }
}

먼저 구슬을 없애는 인덱스를 구하는 수식을 살펴보자.

다음과 같이 맵에 보기 쉽게 순서를 적어보았다.

여기서 상하좌우의 숫자를 순서대로 보자.

7, 22

3, 14

1, 10

5, 18

음,,, 잘 안보이는 것 같다. 다시 더 크게 그려보겠다.

7, 22, 45

3, 14, 33

1, 10, 27

5, 18, 39

이제 좀 잘 보이는 것 같다. 혹시 규칙을 찾았는가??

각 수의 차이를 살펴보면

(7), 15, 23

(3), 11, 19

(1), 9, 17

(5), 13, 21

오 각 차이가 등차를 이룬다. 즉 계차수열 공식을 통해 일반항을 도출할 수 있다는 얘기이다.

잘 모르겠다면 직접 9개 맵까지 그려보자

 

그럼 다음 공식을 사용하여 구할 수 있다.

여기서 a는 초기항을 의미한다. 즉 1, 3, 5, 7을 넣으면 된다.

만약 9, 11, 13, 15가 아닌, 1, 3, 5, 7부터의 수열을 구하고 싶다면

 

이므로,

이렇게 식을 구할 수 있다. 이제 이 식을 정리하면,

이렇게 일반항을 구할 수 있다. 

 

 

투 포인터 방식을 좀 더 보충 설명하자면, 초기에 다음과 같이 시작한다 가정해보자.

 

그럼 왼쪽과 오른쪽 포인터가 가리키는 값이 같으므로 오른쪽이 증가할 것이다. 이렇게 4번 반복되어 5번째 값인 2까지 이동한다.

이 상태가 되면, 오른쪽 인덱스에서 왼쪽 인덱스를 뺀, 즉 왼쪽과 오른쪽 포인터 사이 길이를 체크한다.

 

여기서 길이가 4미만이라면 길이만큼 반복하여 왼쪽 포인터가 가리키는 값을 새 리스트에 넣어준다.

만약 4이상이라면 새 리스트에 넣지 않고 그냥 1번 구슬의 폭발 카운트를 4만큼 증가시켜준다.

 

이후 다음과 같이 왼쪽 포인터를 오른쪽으로 다시 옮긴다.

 

회고

문제가 어렵지 않았지만, 너무 번거로운 구현 문제였다.