문제

BOJ 11559, puyo puyo

핵심

• 입력의 크기가 작으므로 구현에 초점을 맞춘다.
• 뿌요뿌요 게임을 구현하는 문제다. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 한꺼번에 없어지고 1연쇄가 된다. 뿌요들이 없어지고 나서 그 위에 뿌요가 있다면 아래로 떨어지고 또 4개 이상 연결되어 있으면 한 번에 없어지면서 2연쇄가 된다. 이렇게 반복할 때 몇 연쇄가 되는지 구해야 한다.
• 크게 2가지 구현 사항이 있다. 첫째로 뿌요 4개 이상 연결되었는지 판단하고, 연결되어 있다면 지워야 한다. 연결 여부를 판단하기 위해 bfs를 사용한다. bfs를 위한 큐와 거처 간 경로를 저장하기 위한 큐 두 개를 선언하여 4개 이상 연결되었다면 거쳐 간 경로를 순회하며 이를 지운다.

bool erase(int y, int x, char c) {
	queue<pair<int, int>> q;
	queue<pair<int, int>> path;
	isVisited[y][x] = true;
	q.push({y, x});
	bool canErase = false;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		path.push(cur);
		for (int dir = 0; dir < 4; ++dir) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];
			if (ny < 0 || ny >= 12 || nx < 0 || nx >= 12)
				continue;
			if (board[ny][nx] != c || isVisited[ny][nx])
				continue;
			isVisited[ny][nx] = true;
			q.push({ny, nx});
		}
	}	
	if (path.size() >= 4)
		canErase = true;
	while (!path.empty()) {
		auto cur = path.front(); 
		if (canErase)
			board[cur.first][cur.second] = '.';
		path.pop();
	}
	return canErase;
}

• 둘째로 4개 이상 연결된 뿌요를 지우고 나서 이를 바닥으로 떨어뜨려야 한다. 이를 위해 재귀함수를 사용하여 맨 밑바닥에 도착했거나 바로 아래가 비어있지 않다면 종료 조건으로 하여 다음과 같이 구현하였다.

void drop(int row, int col) {
	if (row >= 12 || board[row + 1][col] != '.')
		return ;
	board[row + 1][col] = board[row][col];
	board[row][col] = '.';
	drop(row + 1, col);
}

개선

코드

시간복잡도

• $O(n \times m \times n \times m ..)$

C++

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

string board[14];
int dy[] = {-1, 0, 1, 0}; 
int dx[] = {0, 1, 0, -1};
bool isVisited[14][14];
void drop(int row, int col) {
	if (row >= 12 || board[row + 1][col] != '.')
		return ;
	board[row + 1][col] = board[row][col];
	board[row][col] = '.';
	drop(row + 1, col);
}

bool erase(int y, int x, char c) {
	queue<pair<int, int>> q;
	queue<pair<int, int>> path;
	isVisited[y][x] = true;
	q.push({y, x});
	int cnt = 0;
	bool canErase = false;
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		path.push(cur);
		++cnt;
		for (int dir = 0; dir < 4; ++dir) {
			int ny = cur.first + dy[dir];
			int nx = cur.second + dx[dir];
			if (ny < 0 || ny >= 12 || nx < 0 || nx >= 12)
				continue;
			if (board[ny][nx] != c || isVisited[ny][nx])
				continue;
			isVisited[ny][nx] = true;
			q.push({ny, nx});
		}
	}	
	if (cnt >= 4)
		canErase = true;
	while (!path.empty()) {
		auto cur = path.front(); 
		if (canErase)
			board[cur.first][cur.second] = '.';
		path.pop();
	}
	return canErase;
}

bool bomb() {
	bool isBoomed = false;
	for (int i = 0; i < 12; ++i) {
		for (int j = 0; j < 6; ++j) {
			if (board[i][j] != '.') {
				if (erase(i, j, board[i][j]))
					isBoomed = true;
			}
		}
	}
	return isBoomed;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for (int i = 0; i < 12; ++i)
		cin >> board[i];
	int ans = 0;
	while (1) {
		for (int i = 0; i < 12; ++i) 
			fill(isVisited[i], isVisited[i] + 6, 0);
		if (!bomb()) 
			break;
		for (int col = 0; col < 6; ++col) {
			for (int row = 11; row >= 0; --row) {
				if (board[row][col] != '.')
					drop(row, col);		
			}
		}
		++ans;
	}
	cout << ans;
}

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static char[][] board = new char[14][14];
    static int dy[] = {-1, 0, 1, 0};
    static int dx[] = {0, 1, 0, -1};
    static boolean[][] isVisited = new boolean[14][14];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 12; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < 6; j++)
                board[i][j] = line.charAt(j);
        }
        int ans = 0;
        while (true) {
            for (int i = 0; i < 12; ++i) {
                for (int j = 0; j < 6; ++j)
                    isVisited[i][j] = false;
            }
            if (!bomb())
                break;
            for (int col = 0; col < 6; ++col) {
                for (int row = 11; row >= 0; --row)
                    if (board[row][col] != '.')
                        drop(row, col);
            }
            ++ans;
        }
        System.out.println(ans);
        sc.close();
    }

    static boolean bomb() {
        boolean isBoomed = false;
        for (int i = 0; i < 12; ++i) {
            for (int j = 0; j < 6; ++j) {
                if (board[i][j] != '.') {
                    if (erase(i, j, board[i][j]))
                        isBoomed = true;
                }
            }
        }
        return isBoomed;
    }

    static boolean erase(int y, int x, char c) {
        Queue<int[]> q = new LinkedList<>();
        Queue<int[]> path = new LinkedList<>();
        isVisited[y][x] = true;
        q.add(new int[]{y, x});
        boolean canErase = false;
        while (!q.isEmpty()) {
            var cur = q.poll();
            path.add(cur);
            for (int dir = 0; dir < 4; ++dir) {
                int ny = cur[0] + dy[dir];
                int nx = cur[1] + dx[dir];
                if (ny < 0 || ny >= 12 || nx < 0 || nx >= 6)
                    continue;
                if (board[ny][nx] != c || isVisited[ny][nx])
                    continue;
                isVisited[ny][nx] = true;
                q.add(new int[]{ny, nx});
            }
        }
        if (path.size() >= 4)
            canErase = true;

        while (!path.isEmpty()) {
            var cur = path.poll();
            if (canErase)
                board[cur[0]][cur[1]] = '.';
        }
        return canErase;
    }

    static void drop(int row, int col) {
        if (row >= 12 || board[row + 1][col] != '.')
            return;
        board[row + 1][col] = board[row][col];
        board[row][col] = '.';
        drop(row + 1, col);
    }
}