[ 백준 11559 ] Puyo Puyo (C++)

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

11559번: Puyo Puyo

 

dfs를 이용한 재밌는 구현 문제였다. 규칙을 만들고 그대로 구현하기만 하면 되는 문제라 크게 설명할 것은 없다.

 

인접한 동일 색깔의 개수를 count라고 했을때, dfs 결과 count가 4 이상인 것은 map에서 삭제해주고 붕 떠 있는 것을 아래로 내려주면 된다. 말로 하면 좀 헷갈리니 사진으로 확인하자. 아래는 문제의 테스트 케이스를 돌렸을때 첫 번째 연쇄 과정이다. 

 

 

4개 이상 인접한 문자가 R 뿐이므로 R은 삭제되고, 붕 떠있는 Y는 아래로 내려왔다. 따라서 이를 구현하기 위해 dfs 함수, 삭제하는 함수, 내려주는 함수가 필요하다. dfs만 함수화하고 나머지 두 개는 그냥 메인 함수에 적었다. 하나씩 살펴보자.

 

 

1) dfs 함수

 

void dfs(int row, int col, int& count, char c, stack<pair<int, int>>& s) {
	count++;
	visit[row][col] = 1;
	s.push({ row, col });

	for (int i = 0; i < 4; i++) {
		int m_row = row + move_row[i];
		int m_col = col + move_col[i];
		if (m_row >= 1 && m_row <= 12 && m_col >= 1 && m_col <= 6) {
			if (!visit[m_row][m_col] && map[m_row][m_col] == c) {
				dfs(m_row, m_col, count, c, s);
			}
		}
	}
}

 

전형적인 dfs 형태다. 특이한 점은 스택이 있다는거.. 스택을 추가해준 이유는 삭제해주는 함수에서 설명한다. 그 외에는 dfs 그자체라서 특별히 설명할 것은 없다. 이동한 위치가 범위를 만족하는지, 방문여부와 문자 일치 여부만 확인해주고 재귀적으로 돌려주면 된다.

 

 

2) 삭제 및 내려주는 코드

 

if (count >= 4) {
    // 연쇄작용 - 없어짐
    check = 1; // 연쇄작용 한다는 의미
    for (int cnt = 0; cnt < count; cnt++) {
        row = s.top().first;
        col = s.top().second;
        s.pop();
        map[row][col] = '.';
    }
    
    // 붕 떠있는거 아래로 내려줌
    for (int row = 12; row >= 1; row--) {
        for (int col = 1; col <= 6; col++) {
            if (map[row][col] == '.') {
                int up_row = row - 1; // 동일 열 위에 검사
                while (up_row != 0) {
                    if (map[up_row][col] != '.') {
                        swap(map[up_row][col], map[row][col]);
                        break;
                    }
                    up_row--;
                }
            }
        }
    }
}

 

dfs 결과 count가 4 이상이면 삭제해줘야 한다. 삭제할 위치를 저장해놔야 하기 때문에 스택 자료구조를 썼다. count만큼 스택에서 위치를 뽑아낸 뒤 map에서 '.'으로 만들어주면 된다.

 

아래로 내려주는 함수는 가장 아래행부터 첫행까지 검사하면서 '.'을 만나면 동일 열 위에 문자가 있는지 검사하고, 문자가 있으면 swap해주고 없으면 패스하면 된다.  

 

가장 위에 있는 check 변수는 연쇄작용 여부를 알려주는 변수다. 정답 코드를 보면 알겠지만 check 값을 기준으로 map의 탐색이 반복된다. 즉, while문이 한 번 돌아갈때마다 연쇄작용이 한 번 일어난다는 뜻이므로 특정 변수값(chain)에 1씩 더해주면 이게 정답이 된다. 나머지는 정답 코드를 참고하자.

 

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

char map[13][7];
int visit[13][7];
char c;
int move_row[4] = { 1,-1,0,0 };
int move_col[4] = { 0,0,1,-1 };

void init() {
	// visit 0으로 초기화
	for (int i = 1; i <= 12; i++)
		for (int j = 1; j <= 6; j++)
			visit[i][j] = 0;
}

void dfs(int row, int col, int& count, char c, stack<pair<int, int>>& s) {
	count++;
	visit[row][col] = 1;
	s.push({ row, col });

	for (int i = 0; i < 4; i++) {
		int m_row = row + move_row[i];
		int m_col = col + move_col[i];
		if (m_row >= 1 && m_row <= 12 && m_col >= 1 && m_col <= 6) {
			if (!visit[m_row][m_col] && map[m_row][m_col] == c) {
				dfs(m_row, m_col, count, c, s);
			}
		}
	}
}

int main() {
	
	for (int i = 1; i <= 12; i++)
		for (int j = 1; j <= 6; j++)
			cin >> map[i][j];

	int check = 1;
	int chain = -1;
	stack<pair<int, int>> s;
	int row, col;

	while (check) {
		check = 0;
		++chain;
		init(); // visit 초기화
		for (int i = 1; i <= 12; i++) {
			for (int j = 1; j <= 6; j++) {
				if (!visit[i][j] && map[i][j] != '.') {
					int count = 0;
					dfs(i, j, count, map[i][j], s);
					
					if (count >= 4) {
						// 연쇄작용 - 없어짐
						check = 1;
						for (int cnt = 0; cnt < count; cnt++) {
							row = s.top().first;
							col = s.top().second;
							s.pop();
							map[row][col] = '.';
						}
						
						// 붕 떠있는거 아래로 내려줌
						for (int row = 12; row >= 1; row--) {
							for (int col = 1; col <= 6; col++) {
								if (map[row][col] == '.') {
									int up_row = row - 1;
									while (up_row != 0) {
										if (map[up_row][col] != '.') {
											swap(map[up_row][col], map[row][col]);
											break;
										}
										up_row--;
									}
								}
							}
						}
					}

					else {
						// 연쇄작용 안하면 스택에서 빼줌
						for (int cnt = 0; cnt < count; cnt++)
							s.pop();
					}
				}
			}
		}
	}

	cout << chain << endl;

	return 0;
}