[백준 / 골드1] 21611번 마법사 상어와 블리자드 (Java)

행렬을 리스트로 변환하여 풀이하면 접근하기 쉬울 때가 있다.

문제 보기

사용한 것

• 문제에서 주어지는 행렬, 효율적인 풀이를 위한 ArrayList
• matrixToList() : 행렬을 리스트로 변환.
• listToMatrix() : 리스트를 행렬로 변환.
  • 두 메소드의 행렬의 정 중앙부터 시작해서 나선형으로 증가하는 인덱스를 다루기위한 로직은 다음과 같다.
    • length 가 1부터 시작하여 왼쪽부터 length만큼 이동하고 왼쪽 -> 아래와 같이 방향을 전환
    • 방향 전환을 2회 하면 length를 1 증가
• dirChange() : 방향 변환. (앞에 두 메소드에 사용)
• blizzard() : 구슬 파괴.
• boom() : 구슬 파괴 후 연속적인 폭발.
• change() : 폭발이 끝난 후 구슬들을 변환.

풀이 방법

• 편의를 위하여 상어의 위치에 0 대신 -1을 넣어준다.
• 입력 받은 M 만큼 for 문을 돌아 블리자드 진행하여 얻은 점수를 answer에 계속 증가 시킴
• for 문 안에 내용은 다음과 같다.
  1. blizzard()를 실행하여 범위안에 인덱스를 0으로 만든다. (구슬 파괴)
  2. matrixToList()를 실행하여 행렬인 구슬 정보들을 리스트로 변환한다.
  3. boom()을 실행하여 폭파할 구슬이 없을 때 까지 4개 이상의 연속적인 구슬들을 폭파시키고 얻은 점수를 answer에 더한다.
  4. change()를 실행하여 boom()까지 진행 된 리스트를 조건에 맞게 변화시킨다.
  5. listToMatrix()를 실행하여 블리자드가 진행 된 리스트를 다시 행렬로 변환한다.
• for 문이 끝나면 answer를 반환.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {

    static final int UP = 1;
    static final int DOWN = 2;
    static final int LEFT = 3;
    static final int RIGHT = 4;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] size = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();
        int N = size[0];
        int M = size[1];
        int userIdx = N / 2;

        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            int[] row = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
            matrix[i] = row;
        }
        matrix[userIdx][userIdx] = -1;

        int[][] blizzards = new int[M][2];
        for (int i = 0; i < M; i++) {
            int[] blizzard = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
            blizzards[i] = blizzard;
        }

        int answer = 0;
        for (int[] blizzard : blizzards) {
            blizzard(matrix, userIdx, blizzard[0], blizzard[1]);
            List<Integer> list = matrixToList(matrix, userIdx);
            answer += boom(list);
            list = change(N, list);
            matrix = listToMatrix(list, N, userIdx);
        }

        System.out.println(answer);
    }

    public static List<Integer> matrixToList(int[][] matrix, int userIdx) {
        List<Integer> list = new ArrayList<>();
        int curX = userIdx;
        int curY = userIdx;
        int dir = LEFT;
        int length = 1;
        int move = 0;
        int corner = 0;
        while (curX != 0 || curY != -1) {
            list.add(matrix[curX][curY]);

            if (move == length) {
                dir = dirChange(dir);
                corner++;
                move = 0;
            }

            if (corner == 2) {
                length++;
                corner = 0;
            }

            switch (dir) {
                case UP:
                    curX--;
                    break;
                case DOWN:
                    curX++;
                    break;
                case LEFT:
                    curY--;
                    break;
                default:
                    curY++;
                    break;
            }

            move++;
        }

        list.removeAll(Collections.singletonList(0));
        return list;
    }

    public static int[][] listToMatrix(List<Integer> list, int N, int userIdx) {
        int[][] matrix = new int[N][N];
        int curX = userIdx;
        int curY = userIdx;
        int dir = LEFT;
        int length = 1;
        int move = 0;
        int corner = 0;
        for (int i = 0; i < list.size(); i++) {
            matrix[curX][curY] = list.get(i);

            if (move == length) {
                dir = dirChange(dir);
                corner++;
                move = 0;
            }

            if (corner == 2) {
                length++;
                corner = 0;
            }

            switch (dir) {
                case UP:
                    curX--;
                    break;
                case DOWN:
                    curX++;
                    break;
                case LEFT:
                    curY--;
                    break;
                default:
                    curY++;
                    break;
            }

            move++;
        }

        return matrix;
    }
    
    public static int dirChange(int dir) {
        switch (dir) {
            case UP:
                return LEFT;
            case DOWN:
                return RIGHT;
            case LEFT:
                return DOWN;
            default:
                return UP;
        }
    }

    public static void blizzard(int[][] matrix, int userIdx, int dir, int range) {
        for (int i = 1; i <= range; i++) {
            switch (dir) {
                case UP:
                    matrix[userIdx - i][userIdx] = 0;
                    break;
                case DOWN:
                    matrix[userIdx + i][userIdx] = 0;
                    break;
                case LEFT:
                    matrix[userIdx][userIdx - i] = 0;
                    break;
                default:
                    matrix[userIdx][userIdx + i] = 0;
                    break;
            }
        }
    }

    public static int boom(List<Integer> list) {
        int totalScore = 0;
        while (true) {
            int score = 0;
            int same = 1;
            int lastNum = 0;
            int curNum;
            for (int i = list.size() - 1; i >= 0; i--) {
                curNum = list.get(i);
                if (curNum == lastNum) {
                    same++;
                } else {
                    if (same >= 4) {
                        score += lastNum * same;
                        list.subList(i + 1, i + same + 1).clear();
                    }
                    same = 1;
                }
                lastNum = curNum;
            }

            if (score == 0) {
                break;
            }

            totalScore += score;
        }

        return totalScore;
    }

    public static List<Integer> change(int N, List<Integer> list) {
        int curNum;
        int lastNum = list.get(list.size() - 1);
        int same = 1;
        for (int i = list.size() - 2; i >= 0; i--) {
            curNum = list.get(i);
            if (curNum == lastNum) {
                same++;
            } else {
                if (same == 1) {
                    list.add(i + 2, lastNum);
                    list.set(i + 1, same);
                } else if (same == 2) {
                    list.set(i + 2, lastNum);
                    list.set(i + 1, same);
                } else {
                    list.remove(i + 3);
                    list.set(i + 2, lastNum);
                    list.set(i + 1, same);
                }

                same = 1;
            }

            lastNum = curNum;
        }

        int maxSize = N * N;
        return list.size() > maxSize ? new ArrayList<>(list.subList(0, maxSize)) : list;
    }
}