[알고리즘 문제] 백준11559 - Puyo Puyo

문제 자체는 이해하기 쉽다. 뿌요뿌요 게임을 한번 해봤더라면, 바로 이해할 수가 있다.

 

같은 색깔의 블럭이 상하좌우로 4개 이상 연결되어 있으면 연결되어 있는 모든 같은 색깔의 한꺼번에 없어진다. 그 후, 없어진 공간만큼 위의 블럭들이 아래로 내려오게 된다. 

 

문제는 현재 상황에서 몇번의 연쇄작용(4개이상 상하좌우로 연결된 같은 블럭이 한꺼번에 없어지는 것)이 일어나는지 출력하는 문제이다. 만약 하나도 터지지 않으면 0을 출력한다. 

 

사실 문제는 그렇게 어렵지 않다, 하지만 이걸 코드로 어떻게 옮기느냐가 중요한데 나는 dfs를 활용하여 풀었다.

 

전체적인 흐름은 다음과 같다.

1. 그룹이 하나도 없을 때까지 while문을 수행한다.

2. 현재 상황에서 같은 색깔의 그룹을 모두 '?'로 표시한다(dfs)

3. '?'로 표시된 블럭을 모두 없애고, 없앤 구역만큼 나머지 블럭의 자리를 수정해준다.

4. 다시 1번을 반복한다.

 

코드에서 메인 함수를 제외하고 총 4개의 함수를 사용하였다.

dfs() : X색깔을 기준으로 그룹이 만들어 지는지 검사,

colorCheck() : 그룹을 '?'로 표시

move() : '?'로 표시된 색깔을 없애고, 나머지 블럭들의 위치를 수정

hasGroup() : 현재 상황에서 그룹의 존재여부를 결정

 

import java.util.*;

public class Main {

    // 우,하,좌,상
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static boolean[][] check;
    static char[][] arr = new char[12][6];
    static int groupColorCount = 0;
    static List<Integer> yPosition = new ArrayList<Integer>();
    static List<Integer> xPosition = new ArrayList<Integer>();
    static int result = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int y, x;

        for (y = 11; y >= 0; y--) {
            String s = sc.next();
            for (x = 0; x < 6; x++) {
                arr[y][x] = s.charAt(x);
            }
        }

        if (!hasGroup()) { // 그룹이 하나라도 존재하지 않으면 0출력 후, return;
            System.out.println(0);
            return;
        }

        while (hasGroup()) { // group이 존재할 때 까지 반복
            for (y = 0; y < 12; y++) {
                for (x = 0; x < 6; x++) {
                    if (arr[y][x] != '.' && arr[y][x] != '?') {
                        groupColorCount = 0;
                        yPosition.clear();
                        xPosition.clear();

                        check = new boolean[12][6];
                        dfs(y, x, arr[y][x]);

                        if (groupColorCount >= 4) { // X 색깔을 탐색하여, 블럭이 4개 이상 모이면 '?'로 체크함.
                            colorCheck();
                        }
                    }
                }
            }
            move(); // 현 상황에서 그룹을 모두 찾으면, 그룹을 제거하고 블럭을 떨어뜨림
        }
        System.out.println(result);
    }

    static void dfs(int y, int x, char color) { // 각각의 알파벳을 기준으로 dfs탐색, groupColorCount을 사용한다.

        groupColorCount++;
        check[y][x] = true;
        yPosition.add(y);
        xPosition.add(x);

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (newX < 0 || newX > 5 || newY < 0 || newY > 11 || arr[newY][newX] != color) {
                continue;
            }
            if (arr[newY][newX] == color && !check[newY][newX]) {
                dfs(newY, newX, color);
            }
        }
    }

    static void colorCheck() { // 그룹에 속해있는 블럭을 '?'로 바꿈
        for (int i = 0; i < yPosition.size(); i++) {
            arr[yPosition.get(i)][xPosition.get(i)] = '?';
        }
    }

    static void move() { // 그룹이 없어지고, 블럭을 아래로 떨어뜨림

        boolean[] heights = new boolean[6];
        boolean check;
        int x, y;

        for (x = 0; x < 6; x++) { // 각 x축에서 '?'가 있는 곳을 체크
            for (y = 0; y < 12; y++) {
                check = false;
                if (arr[y][x] == '?') {
                    heights[x] = true;
                }
            }
        }

        for (x = 0; x < 6; x++) {
            if (!heights[x]) {
                continue;
            }
            for (y = 0; y < 12; y++) {
                if (arr[y][x] != '?' && arr[y][x] != '.') {
                    while (y > 0 && arr[y - 1][x] == '?') { // 실제로 블럭을 떨어뜨리는 부분, 현재 블럭을 기준으로 아래 블럭이 '?'이 아닐때까지 반복
                        char temp;
                        temp = arr[y - 1][x];
                        arr[y - 1][x] = arr[y][x];
                        arr[y][x] = temp;
                        y--;
                    }
                }
            }
            for (y = 0; y < 12; y++) { // '?'부분은 '.'로 바꿈
                if (arr[y][x] == '?') {
                    arr[y][x] = '.';
                }
            }
        }
        result++; // 한번 연쇄작용이 발생하였음
    }

    static boolean hasGroup() { // 그룹이 존재하는지 검사, dfs()사용

        int y, x;

        for (y = 0; y < 12; y++) {
            for (x = 0; x < 6; x++) {
                if (arr[y][x] != '.' && arr[y][x] != '?') {
                    groupColorCount = 0;
                    check = new boolean[12][6];
                    dfs(y, x, arr[y][x]);

                    if (groupColorCount >= 4) { // 없앨 수 있는 그룹이 있으면 return true;
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

코드가 생각보다 긴데, 크게 함수로 나누어 났기 때문에 각 함수의 역할만 제대로 이해한다면 크게 어렵지 않은 코드이다.

 

몇가지 특징점을 살펴보자면,

1. 입력받을 때, 사람의 입장에서 보기 편하게 하기 위해 Y축을 반대로 하여 입력받았다.

 

2. 메인 함수에서, while()문의 조건에 함수를 넣어서 각 loop마다 그룹이 존재하는지 검사하였다.

 

3. dfs함수에서는 X색상 주변에 X색상이 있는지 검사하고, 이때 주변 블럭의 x,y좌표를 list에 저장하였다, 이 값은 main함수에서 사용한다.

 

4. 블럭의 위치를 수정하는 부분에서 시간을 많이 잡아먹었는데, 공백(블럭이 없어지고 남은 빈공간)이 나머지 블럭의 아래,위, 사이에 있는 것을 생각해야 했기 때문이다. 코드가 난해할 수 있는데, 풀어 설명하면 현재 블럭에서 y--방향으로 이동하면서 빈 공간과 위치를 바꿔간다.

이후, 각 블럭마다 이 작업이 모두 끝났으면 '?' 부분을 모두 '.'로 바꾸어 준다. 그리고 연쇄작용++