BOJ 11559 - Puyo Puyo(DFS, BFS, 배열 조작, 구현) C++, Java 풀이

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

11559번: Puyo Puyo

- 전형적인 구현 문제이지만 생각보다 정확하고 빠르게 풀기 힘들었던 문제이다. 한 턴에 연쇄가 여러 번 일어나도 1연쇄로 카운트 되므로 한 턴에 모든 연쇄에 대해서 처리한 다음 블럭을 아래로 내리면 된다. 

C++은 dfs, Java는 bfs로 풀이하였다.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

string a[12];
bool check[12][6];
int ans = 0;

void go(char ch, int r, int c, vector<pii> &v) {
    if (0 > r || 0 > c || r >= 12 || c >= 6 || check[r][c] || a[r][c] != ch) return;
    v.push_back({r, c});
    check[r][c] = true;

    for (int i = 0; i < 4; ++i) {
        go(ch, r + dr[i], c + dc[i], v);
    }
}

void down() {
    for (int i = 10; i >= 0; --i) {
        for (int j = 0; j < 6; ++j) {
            if (a[i][j] != '.') {
                int r = i;
                while (1) {
                    if (r == 11 || a[r + 1][j] != '.') break;
                    ++r;
                }
                swap(a[r][j], a[i][j]);
            }
        }
    }
}

int main() {
    FASTIO;
    for (int i = 0; i < 12; ++i) {
        cin >> a[i];
    }
    while (1) {
        memset(check, false, sizeof(check));
        bool stop = true;
        for (int i = 0; i < 12; ++i) {
            for (int j = 0; j < 6; ++j) {
                vector<pii> v;
                if (a[i][j] != '.' && !check[i][j]) go(a[i][j], i, j, v);
                if (v.size() >= 4) {
                    stop = false;
                    for (auto &[r, c] : v) {
                        a[r][c] = '.';
                    }
                }
            }
        }
        if (stop) break;
        ++ans;
        down();
    }

    cout << ans;
    return 0;
}

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

public class Puyo_Puyo {
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };

    static int ans = 0;
    static char[][] a = new char[12][6];
    static boolean[][] check = new boolean[12][6];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 12; ++i) {
            a[i] = br.readLine().toCharArray();
        }

        while (true) {
            for (boolean[] c : check) {
                Arrays.fill(c, false);
            }
            boolean go = false;
            for (int i = 0; i < 12; ++i) {
                for (int j = 0; j < 6; ++j) {
                    if (a[i][j] == '.')
                        continue;
                    boolean flag = bfs(i, j);
                    if (flag)
                        go = true;
                }
            }
            if (!go)
                break;

            ++ans;
            down();
        }
        System.out.println(ans);
    }

    static boolean bfs(int sr, int sc) {
        List<Pair> list = new ArrayList<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(sr, sc));
        check[sr][sc] = true;
        list.add(new Pair(sr, sc));

        while (!q.isEmpty()) {
            Pair p = q.poll();
            for (int i = 0; i < 4; ++i) {
                int nr = p.r + dr[i];
                int nc = p.c + dc[i];
                if (0 > nr || 0 > nc || 12 <= nr || 6 <= nc)
                    continue;
                if (check[nr][nc] || a[nr][nc] != a[sr][sc])
                    continue;

                q.add(new Pair(nr, nc));
                check[nr][nc] = true;
                list.add(new Pair(nr, nc));
            }
        }

        if (list.size() >= 4) {
            for (Pair p : list) {
                a[p.r][p.c] = '.';
            }
        }

        return list.size() >= 4;
    }

    static void down() {
        for (int i = 10; i >= 0; --i) {
            for (int j = 0; j < 6; ++j) {
                int r = i;
                while (r + 1 < 12 && a[r + 1][j] == '.') {
                    ++r;
                }
                if (r != i) {
                    a[r][j] = a[i][j];
                    a[i][j] = '.';
                }
            }
        }
    }

    static class Pair {
        int r, c;

        Pair(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}