[백준 11559번] Puyo Puyo (Java)

[백준 11559번 Puyo Puyo URL]

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

문제를 풀기위해 생각해야할 것은 다음과 같습니다.

1. 상하좌우 인접한 뿌요가 4개 이상일 경우 터진다.

이 조건으로 인해 BFS탐색을 하면서 각 뿌요의 좌표를 저장해야 합니다. 뿌요의 수가 4개 이상일 경우에는

해당 뿌요들의 자리를 '.' 으로 교체하는 것이 뿌요를 터뜨리는 행위입니다.

그렇기 때문에 뿌요의 좌표와 갯수를 파악하기 쉬운 자료구조는 List입니다.

2. 한 라운드에 4개 이상인 뿌요가 여러 개 있다하더라도 연쇄반응은 1회로 간주한다.

이 조건으로 인해 반복문을 돌릴 때 연쇄반응을 카운트하는 ans 변수의 증가 타이밍을 잘 잡아야 합니다.

3. 한 라운드가 끝난 뒤에 남아있는 모든 뿌요들을 아래방향(땅)으로 모두 내린다.

이 조건 또한 타이밍을 잘 잡아야 합니다. 

(4개 이상의 뿌요들은 동시에 터지기때문에 한 라운드가 끝난 뒤 땅으로 떨어뜨려야합니다.)

코드를 살펴보면,

1. sovle() 메소드 내에서 while(true) 반복을 하고 있습니다. 이때 while루프 한 번이 한 라운드이며

라운드를 빠져나오는 조건은 12 X 6 의 2차원 배열 map 모두 탐색하며 BFS를 돌린 후에

List의 사이즈가 4이상이 한번도 되지 않은 경우, 더 이상 뿌요를 터뜨릴 수 없다고 간주해 while문을 빠져나온다.

2. while문 내에서 12 X 6의 2차원 배열을 탐색하며 map[row][col] != '.' 인 경우 뿌요이므로 그 좌표부터

BFS탐색을 시작합니다.

3. 한번의 BFS 탐색이 끝나면 List의 사이즈가 4이상인지 확인하고 4이상이라면 모든 뿌요들의 좌표를 통해

map[row][col] = '.' 로 대체합니다. 그 이후 다음의 BFS탐색을 위해 List를 초기화합니다.

4. 한 라운드가 끝나면 toGround 메소드를 통해 남아있는 뿌요들을 땅으로 내립니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static char[][] map;
    public static boolean[][] visited;
    public static List<Node> list;
    public static int N = 12, M = 6, ans = 0;
 
    public static void main(String[] args) throws Exception {
 
        map = new char[N][M];
        visited = new boolean[N][M];
        list = new ArrayList<Node>();
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
            }
        }
        solve();
        System.out.println(ans);
 
    }
 
    //모든 뿌요들을 땅으로 내려보내는 메소드
    public static void toGround() {
 
        for (int i = 0; i < M; i++) {
            for (int j = N - 1; j > 0; j--) {
 
                if (map[j][i] == '.') {
 
                    for (int k = j - 1; k >= 0; k--) {
                        if (map[k][i] != '.') {
                            map[j][i] = map[k][i];
                            map[k][i] = '.';
                            break;
                        }
                    }
                }
            }
        }
 
    }
 
    public static void solve() {
 
        while (true) {
            
            //while문을 탈출하기 위한 flag와 visited 배열 초기화
            boolean flag = true;
            for (int i = 0; i < N; i++)
                Arrays.fill(visited[i], false);
 
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!visited[i][j] && map[i][j] != '.')
                        bfs(i, j);
 
                    //BFS 탐색을 한번 하고 난 뒤 list의 크기가 4이상일 경우 해당 뿌요들을 터뜨린다.
                    if (list.size() >= 4) {
                        flag = false;
                        for (Node node : list) {
                            map[node.row][node.col] = '.';
                        }
                    }
                    //4개 이상 인접한 한가지 색깔의 뿌요를 터뜨렸으면 List를 초기화해야 한다.
                    list.clear();
                }
            }
            toGround();
            if (flag)
                break;
            else
                ans += 1;
            
        }
    }
    
    //해당 지점부터 BFS탐색을 시작하는 메소드
    public static void bfs(int startRow, int startCol) {
 
        Queue<Node> q = new LinkedList<Node>();
        
        visited[startRow][startCol] = true;
        char val = map[startRow][startCol];
        q.offer(new Node(startRow, startCol));
        
        //같은 뿌요가 4개가 인접한 경우 연쇄반응이 일어나야 하므로 list에 저장시킨다.
        //list의 크기가 4이상이면 for문을 통해 터뜨린다.
        list.add(new Node(startRow, startCol));
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && map[nr][nc] == val) {
                    list.add(new Node(nr, nc));
                    q.offer(new Node(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
        
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < M);
    }
 
}
 
class Node {
 
    int row;
    int col;
 
    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
 
}