[백준] 11559번 : Puyo Puyo - C++

백준 11559번 : Puyo Puyo

등급 : Gold IV

11559번: Puyo Puyo (acmicpc.net)

11559번: Puyo Puyo

 사용 알고리즘 : DFS

 사용 자료구조 : Vector, Deque

 

백준 페이지에는 알고리즘 분류에 BFS로 나와있는 것을 보아 BFS 구현을 권장하는 것 같은데, DFS로 구현하는 방법이 먼저 떠올라 이대로 진행했다.

 

입력은 12×6의 이차원 행렬로 받는데, 블럭이 깨졌을 때 남은 블럭들이 아래로 내려가는 것을 보아 배열을 erase와 push하기 쉽도록 전치행렬*로 재구성하였다. (이차원 배열의 구조 상 블럭 하나의 push와 pop은 가로로만 이루어질 수 있기 때문)

전치행렬(Transpose Matrix) : m×n행렬을 n×m으로 바꾼 행렬.

.	G	.	.
R	R	.	.
G	R	R	.
G	G	Y	Y
Y	Y	B	B

위와 같은 경우 R블럭이 깨지면 G가 내려오고 나머지가 .으로 채워져야 하는데, 왼쪽과 같이 구현되어 있으면 push와 pop이 행 전체 또는 하나의 열로만 가능하여 블럭이 내려가는 것을 구현하는 데 더 큰 비용이 소모된다. 때문에 아래와 같이 변환된 행렬로 재구성해도록 한다.

.	R	G	G	Y
G	R	R	G	Y
.	.	R	Y	B
.	.	.	Y	B

이후 깨지는 블럭을 임시적으로 다른 문자(본 코드에서는 'X' 이용)로 바꾸고, 과정이 끝나면 한 번에 제거하도록 한다.
그리고 이를 몇 회 반복하는지 측정한다.

코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

bool visit[6][12] = { false };						// T-Matrix의 visit 배열
vector <deque <char>> v;						// erase 이후 윗부분부터 삽입 가능하도록 deque를 사용
vector <pair <int, int>> tmp;						// 깨지는 블럭 위치를 임시로 저장할 배열
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans = 0;

void dfs(int x, int y, int amt, char col)				// 탐색 좌표(x, y)와 같은 블럭 갯수(amt), 블럭 색깔(col)
{
    visit[x][y] = true;
    if (amt == 0) tmp.push_back({ x, y });				// 첫 블럭인 경우 tmp에 바로 삽입
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < 6 && ny < 12)			// 화면의 범위를 벗어나지 않는 경우
        {
            if (!visit[nx][ny])
            {
                if (v[nx][ny] == col)					// visit하지 않은 위치이면서 같은 색깔인 경우 탐색
                {
                    tmp.push_back({ nx, ny });				// tmp 배열에 다음 블럭 위치 삽입
                    dfs(nx, ny, amt + 1, col);				// 다음 위치에 amt를 1 증가시켜 dfs 수행
                }
            }
        }
    }
}

void puyo()								// 파괴될 블럭을 다 탐색한 이후 블럭을 파괴하는 함수
{
    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 12; j++)
        {
            if (v[i][j] == 'X')
            {
                v[i].erase(v[i].begin() + j);				// 'X'위치의 블럭을 erase해 내려가는 효과
                v[i].push_front('.');					// 위쪽에 '.'을 삽입해 블럭이 내려간 이후 화면 재구성
            }
        }
    }
}


int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    v.resize(6, deque <char>(12));
    for (int i = 0; i < 12; i++)					// 배열을 입력받고 변환시켜 저장함
    {
        for (int j = 0; j < 6; j++)
        {
            cin >> v[j][i];
        }
    }
    while (1)
    {
        bool chk = false;						// 블럭 파괴가 있었는지 확인하는 변수
        for (int i = 0; i < 6; i++)
        {
            for (int j = 0; j < 12; j++)
            {
                if (v[i][j] != '.' && v[i][j] != 'X')			// 블럭이 '.'과 'X'가 아닌 경우
                {
                    tmp.clear();					// 임시저장 배열을 클리어함
                    dfs(i, j, 0, v[i][j]);
                    if (tmp.size() >= 4)				// dfs가 끝난 후 블럭 파괴가 필요한 경우 (4개 이상)
                    {
                        for (int k = 0; k < tmp.size(); k++)
                        {
                            v[tmp[k].first][tmp[k].second] = 'X';	// 파괴할 블럭 위치에 'X'를 입력
                            chk = true;					// 블럭 파괴가 있었으므로 true로 변경
                        }
                    }
                }
            }
        }
        if (chk)
        {
            ans++;							// 블럭 파괴가 있던 경우 ans값을 1 증가시켜준다
            puyo();							// 블럭 파괴 실행
            fill_n(visit[0], 72, false);				// 다음 블럭 상태를 조사하기 위해 visit 초기화
        }
        else break;
    }
    cout << ans;
}