[백준] Puyo Puyo (11559) Java

문제 링크

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

11559번: Puyo Puyo

 

문제 요약

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

뿌요뿌요 필드의 입력을 받아서 총 몇 연쇄가 일어나는지 개수를 세자.

 

입력

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

 

출력

현재 주어진 상황에서 몇 연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.

 

접근법

BFS로 소금간을 친 단순 구현 문제이다.

 

1. 현재 필드 상태에서 터질 수 있는 뿌요 그룹을 전부 터트린다. 뿌요 그룹을 찾을 때 BFS로 탐색을 한다.
2. 만약 뿌요가 한개도 터지지 않는다면 연쇄가 끊긴 것임으로 정답을 출력한다.
3. 터진 뿌요가 있다면 빈 공간이 생기므로, 공중에 떠 있는 뿌요가 있다면 빈 공간을 채워가며 내려준다. 연쇄가 하나 추가된다.

위 3단계를 반복하면 끝이다.

 

뿌요 그룹을 찾는 데는 BFS를 활용했다.

여기서 방문 여부, 같은 색깔인지, 상하좌우 탐색을 할 때 필드 밖으로 벗어나지는 않는지 정도만 체크해 주면 된다.

 

공중에 떠있는 뿌요를 내려주는 것은 뭔가 까다로워 보였는데, 막상 구현하려고 보니 생각보다 간단하게 구현이 되었다.

코드와 주석을 보는게 이해가 빠를 것이다.

 

 

시간 복잡도

정확히는 모르겠으나,

필드가 총 72칸인데 빈 공간은 탐색을 안해도 되고, 뿌요는 계속해서 터지고, BFS는 같은 뿌요만 탐색을 하기 때문에

오래 걸릴래야 걸릴 수가 없다. 나는 128ms 걸렸다.

 

 

공간 복잡도

필드를 저장할 char형 2차원 배열, 방문 여부를 저장할 boolean형 2차원 배열 (둘 다 72칸)

사이사이 queue에 들어가는 뿌요들 - 아무리 많아봤자 72개

따라서 공간 복잡도도 매우 작다.

 

 

풀면서 놓쳤던 점

BFS를 구현하는 것이 생각보다 어색했다.

visit 배열에 방문 여부를 언제 표시해야 하는지 - poll() 할 때인지, 아니면 enqueue할 때인지

이런 것들이 아직은 헷갈리는 듯 했다.

BFS 문제를 조금 더 풀어봐야겠다.

 

 

이 문제에서 얻어갈 점

BFS 구현 실력.

 

 

코드

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        char[][] field = new char[12][6];
        boolean[][] visit = new boolean[12][6];

        //입력되는 필드를 2차원 char 배열 형태로 그대로 입력받음
        readField(field);

        int chainCnt = 0;

        while (true)
        {
            //현재 필드 상태에서 터질수 있는 뿌요들을 전부 터트림
            //터진 뿌요 뭉탱이(?)의 개수를 반환
            int boomCnt = boomAllPuyos(field, visit);

            //만약 터진 뿌요가 하나도 없다면 연쇄가 끊긴 것임
            if (boomCnt == 0)
                break;

            //공중에 떠 있는 뿌요가 있다면 빈공간을 채워서 내려줌
            makeAllPuyosDown(field);

            chainCnt++;
        }

        System.out.println(chainCnt);
    }

    static void readField(char[][] field) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        for (int i = 0; i < 12; i++)
        {
            line = br.readLine();
            for (int j = 0; j < 6; j++)
                field[i][j] = line.charAt(j);
        }
    }

    static int boomAllPuyos(char[][] field, boolean[][] visit)
    {
        int boomCnt = 0;
        Queue<Puyo> connectedPuyos = new LinkedList<>();

        for (int row = 0; row < 12; row++)
        {
            for (int col = 0; col < 6; col++)
            {
                //.(빈공간)이 아니고, 방문한 적 없는 뿌요를 찾을 때 까지 필드 탐색
                if (field[row][col] == '.' || visit[row][col])
                    continue;

                visit[row][col] = true; //방문 표시
                //현재 뿌요를 기준으로 주위의 같은 색깔 뿌요를 탐색해 나갈 것임
                connectedPuyos.add(new Puyo(field[row][col], row, col));

                //BFS를 통해 주위에 같은 색깔 뿌요들을 찾아서
                //connectedPuyos Queue에다가 넣어주는 함수
                getConnectedPuyos(field, visit, connectedPuyos);

                //주위 같은색깔 뿌요가 4개 이상이면 터트린다!
                if (connectedPuyos.size() >= 4)
                {
                    for (Puyo p : connectedPuyos)
                        field[p.row][p.col] = '.';
                    boomCnt++;
                }

                //뿌요 뭉탱이 초기화
                connectedPuyos.clear();
            }
        }

        //visit 초기화
        for (boolean[] v : visit)
            Arrays.fill(v, false);

        return boomCnt;
    }

    static void getConnectedPuyos(char[][] field, boolean[][] visit, Queue<Puyo> connectedPuyos)
    {
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //상하좌우 이웃 뿌요들에 접근하기 쉽게 하기 위한 배열
        Puyo pivotPuyo, connectedPuyo;
        int neighborRow, neighborCol;

        //bfsQueue는 이웃 뿌요들을 탐색하기 위한 BFS를 할 때 쓰는 queue이다. 이 함수에서만 사용함.
        //connectedPuyos는 BFS를 통해 같은 색깔 뿌요 뭉탱이들을 찾아서 그 뿌요들을 보관하는 queue
        //connectedPuyos는 boomAllPuyos 함수에서도 사용한다.
        Queue<Puyo> bfsQueue = new LinkedList<>();
        bfsQueue.add(connectedPuyos.peek()); //BFS의 시작이 될 뿌요를 넣어줌

        while (!bfsQueue.isEmpty())
        {
            pivotPuyo = bfsQueue.poll();

            //poll한 뿌요의 상하좌우 뿌요를 확인
            for (int[] dir : dirs)
            {
                neighborRow = pivotPuyo.row + dir[0];
                neighborCol = pivotPuyo.col + dir[1];

                //이 뿌요가 필드 내에 있지 않거나, 같은 색깔 뿌요가 아니거나, 이미 방문한 뿌요인 경우
                if (!isInField(neighborRow, neighborCol) ||
                        field[neighborRow][neighborCol] != pivotPuyo.type ||
                        visit[neighborRow][neighborCol])
                    continue;

                visit[neighborRow][neighborCol] = true;

                //bfs에도, connectedPuyo에도 둘 다 넣어줘야하는 것을 잊지 말자
                connectedPuyo = new Puyo(field[neighborRow][neighborCol], neighborRow, neighborCol);
                bfsQueue.add(connectedPuyo);
                connectedPuyos.add(connectedPuyo);
            }
        }
    }

    static void makeAllPuyosDown(char[][] field)
    {
        int dotCnt;

        //세로줄 단위로 본다
        for (int col = 0; col < 6; col++)
        {
            dotCnt = 0;

            //맨 아래 뿌요부터 위로 하나씩 확인
            for (int row = 11; row >= 0; row--)
            {
                //.(빈공간)의 개수를 센다
                if (field[row][col] == '.')
                {
                    dotCnt++;
                    continue;
                }

                //뿌요를 만났을 때, 이전에 빈공간을 만난 적이 있다면
                //그 개수만큼 아래로 내려주고, 해당 공간은 빈공간으로 바꿔준다
                if (dotCnt != 0)
                {
                    field[row + dotCnt][col] = field[row][col];
                    field[row][col] = '.';
                }
            }
        }
    }

    static boolean isInField(int row, int col)
    {
        return row >= 0 && row < 12 && col >= 0 && col < 6;
    }
}

class Puyo
{
    char type;
    int row;
    int col;

    Puyo(char type, int row, int col)
    {
        this.type = type;
        this.row = row;
        this.col = col;
    }
}