BOJ11559_Puyo Puyo

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

문제정리

1. 룰

(1) 뿌요는 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

(2) 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색

뿌요들이 한꺼번에 없어진다.

(3) 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 아래로 떨어지게 된다.

(4) 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데

터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

(5) 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한

번의 연쇄가 추가된다.

2. 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산

3. map[12][6]이 주어진다. '.'은 빈공간 , R은 빨강 뿌요 , G는 초록 뿌요 , B는 파랑 뿌요 , P는 보라 뿌요

Y는 노랑 뿌요(대문자로 주어진다)

4. 입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다.

5. 현재 주어진 상황에서 몇 연쇄가 되는지 출력하라. 하나도 터지지 않는다면 0을 출력

문제issue

1. 뿌요는 동시에 터진다.

해결흐름

1. 뿌요 없애기

(1) map에서 빈공간이 아니고 , 방문하지 않은 뿌요라면 거기에서 부터 bfs시작해서 연결된

같은 뿌요가 있으면 카운트

(2) 카운트가 4개 이상이면 다시 bfs돌아서 그 위치들을 q에 넣어줌 , 이때 flag = ture

(3) q에 있는 뿌요 위치들 빈공간으로 바꿔줌

2. 뿌요 내리기

(1) 각 열을 기준으로 아래에서 부터 뿌요가 있으면 q에 담기

(2) 맨 아래에서 부터 채워주기

(3) q 크기 이상의 값은 빈공간으로 바꿔주기

3. 연쇄카운트

4. 종료조건

flag = false면 더 이상 없앨 뿌요가 존재x

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    private static boolean flag;
    private static char[][] map;
    private static boolean[][] visited;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new char[12][6];
        visited = new boolean[12][6];
        for (int i = 0; i < 12; i++) {
            String s = br.readLine().trim();
            for (int j = 0; j < 6; j++) {
                map[i][j] = s.charAt(j);
            }
        }
        int result = 0;
        while (true) {
            // 뿌요없애기
            flag = false;
            remove();
            if (flag)
                result++;
            else
                break;
            // 뿌요내리기
            down();
        }
        System.out.println(result);
    } // end of main
 
    private static void down() {
        for (int i = 0; i < 6; i++) {
            Queue<Character> q = new LinkedList<Character>();
            for (int j = 11; j >= 0; j--) {
                if(map[j][i] != '.') {
                    q.add(map[j][i]);
                }
            }
            int q_size = q.size();
            for (int j = 11; j > 11 - q_size; j--) {
                map[j][i] = q.poll();
            }
            if(q_size < 12 && q_size > 0) {
                for (int j = 11 - q_size; j >= 0; j--) {
                    map[j][i] = '.';
                }
            }
        }
    }
 
    static class pair {
        int r;
        int c;
 
        public pair(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }
 
    private static int[] dr = { -1, 0, 1, 0 };
    private static int[] dc = { 0, 1, 0, -1 };
 
    private static void remove() {
        visited = new boolean[12][6];
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (map[i][j] != '.' && !visited[i][j]) {
                    Queue<pair> q = new LinkedList<pair>();
                    Queue<pair> remove_puyo = new LinkedList<pair>();
                    int cnt = 0;
                    visited[i][j] = true;
                    q.add(new pair(i, j));
                    remove_puyo.add(new pair(i, j));
                    while (!q.isEmpty()) {
                        cnt++;
                        pair p = q.poll();
                        int r = p.r;
                        int c = p.c;
                        for (int k = 0; k < 4; k++) {
                            int nr = r + dr[k];
                            int nc = c + dc[k];
                            if (nr >= 0 && nr < 12 && nc >= 0 && nc < 6 && map[nr][nc] == map[r][c]
                                    && !visited[nr][nc]) {
                                q.add(new pair(nr, nc));
                                remove_puyo.add(new pair(nr, nc));
                                visited[nr][nc] = true;
                            }
                        }
                    }
                    // cnt >= 4면 그 위치 빈공간으로 만들기
                    if (cnt >= 4) {
                        flag = true;
                        while(!remove_puyo.isEmpty()) {
                            pair p = remove_puyo.poll();
                            map[p.r][p.c] = '.'; 
                        }
                    }
                }
            }
        }
    }
} // end of class