백준)Q.11559_뿌요뿌요(BFS)

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

11559번: Puyo Puyo

문제

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

 

입력

12*6의 문자가 주어진다.

이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.

R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.(모두 대문자로 주어진다.)

입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태(즉 뿌요 아래에 빈 칸이 있는 경우는 없음) 이다.

 

출력

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

 

예제 입력 1 

......

......

......

......

......

......

......

......

.Y....

.YG...

RRYG..

RRYGG.

 

예제 출력 1 

3

 

<나의 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Q_11559 { // 뿌요뿌요
 
    static int[] dx = { 0, 0, -1, 1 }; // 동서남북 탐색을 위한 배열.
    static int[] dy = { 1, -1, 0, 0 };
    static int count, popcount;
    // count => 터질수 있나 없나(색깔이 4개이상인가)체크.
    // popCount => 몇번 터지나 체크. 최종 return값.
    static boolean poped; // 한번이라도 터졌는지 체크.
    static Queue<Node> q = new LinkedList(); // BFS탐색을 위한 큐.
    static ArrayList<ArrayList<Character>> puyoList = new ArrayList<>();
    // 뿌요map을 담을 Char형 ArrayList
    static ArrayList<Node> saveNode = new ArrayList<>();
    // 터질 노드를 기억할 Node형 ArrayList
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        char[][] puyo = new char[12][6]; // 입력받고 ArrayList에 넘겨줄 (임시)배열
        boolean[][] check = new boolean[6][12]; // visited를 체크할 배열
 
        // 입력받기
        for (int i = 0; i < 12; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < 6; j++) {
                puyo[i][j] = input[j];
            }
        }
 
        // ArrayList에 입력받은 뿌요 담기
        for (int i = 0; i < 6; i++) {
            ArrayList<Character> tmp = new ArrayList<>();
            for (int j = 11; j >= 0; j--) {
                tmp.add(puyo[j][i]);
            }
            puyoList.add(tmp);
        }
 
        boolean marking = false; // 한번이라도 터지는게 있나 체크할 marking 변수
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 12; j++) {
                // 마지막줄이 아닌 줄은 .을 만나는 순간 다음줄 체크
                if (puyoList.get(i).get(j) == '.' && i != 5)
                    break;
 
                // 마지막 노드탐색을 끝내고
                // && 뿌요가 터지는 부분이 한군데라도 있으면(marking이 true면) 아래 실행
                if (i == 5 && j == 11 && marking) {
                    pop(puyoList, check); // pop메소드로 뿌요를 pop시켜준다.
                    check = new boolean[6][12]; // check 초기화
                    i = -1; // main의 for문을 0,0부터 다시 시작한다.
                    j = 0;
                    count = 0; // count초기화
                    saveNode.clear(); // 기억한 Node들을 초기화
                    marking = false;
                    break;
                }
 
                // visited하지 않았고 && '.'이 아닌 색깔이 있으면 아래 실행
                if (!(check[i][j]) && puyoList.get(i).get(j) != '.') {
                    count++;
                    check[i][j] = true;
                    // 해당 노드를 큐에 저장하고 BFS실행
                    q.add(new Node(i, j));
                    bfs(puyoList, check);
 
                    // BFS실행 후 count가 4가 넘으면(뿌요가 터져야 하면) 아래 실행
                    if (count >= 4) {
                        // bfs메소드에서 저장되지 않은 시작노드를 saveNode에 저장
                        saveNode.add(new Node(i, j));
                        // marking을 true로 변경하여 끝까지 탐색이 끝났을때 한꺼번에
                        // pop메소드로 터트려주기
                        marking = true;
                        // count 초기화(이후 노드들을 또 탐색해야 하기 때문)
                        count = 0;
                        continue;
                    }
 
                    // marking이 true인데 이번 count가 4보다 작으면
                    // bfs메소드에서 저장된 saveNode들을 count된 만큼 제거해줌(터질 대상이 아니기 떄문)
                    else if (marking && count < 4) {
                        for (int k = 0; k < count - 1; k++) {
                            saveNode.remove(saveNode.size() - 1);
                        }
                        // count 초기화(이후 노드들을 또 탐색해야 하기 때문)
                        count = 0;
                        continue;
                    }
 
                    // marking이 false이고(터질대상인 애들이 아직 없고) 이번 count가 4미만이면
                    else if (!marking && count < 4) {
                        // 저장된 모든 노드들과 count를 clear.(터질대상이 없으니까=marking이 false니까)
                        saveNode.clear();
                        count = 0;
                    }
 
                }
 
            } // end of for _ j
        } // end of for_i
 
        // 반복문이 종료되고 한번도 pop이 실행되지 않았으면 0 출력.
        if (!poped)
            System.out.println("0");
        else
            System.out.println(popcount);
 
    } // end of main
 
    static void bfs(ArrayList<ArrayList<Character>> list, boolean[][] marked) {
 
        while (!q.isEmpty()) {
            Node current = q.poll();
 
            for (int i = 0; i < 4; i++) {
 
                int nextX = current.x + dx[i];
                int nextY = current.y + dy[i];
 
                if (nextX < 0 || nextY < 0 || nextX >= 6 || nextY >= 12)
                    continue;
 
                if (!(marked[nextX][nextY]) && list.get(current.x).get(current.y) == list.get(nextX).get(nextY)) {
                    marked[nextX][nextY] = true;
                    q.add(new Node(nextX, nextY));
                    count++;
                    // 큐에 넣을 다음 노드를 saveNode에 저장해준다.
                    // 이는 터질 대상이 아니라면 bfs를 호출한 main메소드로 되돌아 갔을때 추가된 만큼 삭제된다.
                    saveNode.add(new Node(nextX, nextY));
                }
 
            }
 
        }
 
    }
 
    static void pop(ArrayList<ArrayList<Character>> list, boolean[][] marked) {
 
        // pop이 적어도 한번은 실행됐음을 체크해줘야함.
        poped = true;
 
        // 기억한 Node들을 3으로 변경
 
        for (int i = 0; i < saveNode.size(); i++) {
            list.get(saveNode.get(i).x).set(saveNode.get(i).y, '3');
        }
 
        // 3으로 변경된 Node들은 .으로 변경(터트림.)
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                if (list.get(i).get(j) == '3') {
                    list.get(i).remove(j);
                    if (j == 0)
                        j = -1;
                    else
                        j--;
                }
            }
        }
 
        // 터진 후 리스트의 길이가 0이면(한줄이 모두 터져서 x의 길이가 6이 아니게 되면)
        // 사라진 줄만큼 .의 줄을 추가해줌
        while (list.size() != 6) {
            ArrayList<Character> tmp = new ArrayList<>();
            tmp.add('.');
            list.add(tmp);
        }
 
        // 마찬가지로 y가 12가 아니면(터진 후 뒤에 버려진 자리들) '.'을 추가해주며 각 y줄을 채워줌.
        for (int i = 0; i < list.size(); i++) {
            while (list.get(i).size() != 12) {
                list.get(i).add('.');
            }
 
        }
 
        // popcount를 증가.
        popcount++;
 
    } // end of pop
 
    // 노드클래스
    static class Node {
        int x, y;
 
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
    } // end of Node class
 
} // end of class

 

보완점

: 뿌요의 입력부분에서 처음부터 ArrayList로 입력이 가능할 듯 함. 

: 중력부분을 Queue를 이용 할 수 있음.