[백준 11559] Puyo Puyo(자바)

안녕하세요 여러분~

solved.ac 기준 5만 투력.

백준 11559번 뿌요뿌요를 가져왔습니다 ㅎㅎ 5만투력 정도면 도내 중위 랭크정도 되겠군요..쿠쿠 :)

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

11559번: Puyo Puyo

---

자 그러면 어떻게 풀어야 할까요?

늘 그랬듯이 우리는 분석, 설계, 구현 요 순서대로 해볼겁니다.

 

우선 분석부터 들어가볼까요?

분석

문제을 읽어보셨다면 대충 구현해야 할 것들을 떠올려 볼 수 있습니다! 

우선 

1, check() >> 뿌요들이 폭파될수 있으면 true, 폭파 될 수 없으면 false 반환해주는 함수. 이때 true면 폭파까지 시켜주기

2, move() >> 뿌요들이 폭파되어 연쇄 작용을 일으킨 후, 아래로 밀어주는 함수.(중력이 작용하니까)

 

이 때 클린코드 관점에서는 check()함수에서 폭파시켜주는 부분은 따로 떼는게 바람직하지만..취향차이입니다 ㅎㅎ

그리고 여기서 유의해야할점은, 뿌요들이 한꺼번에 동시에 폭파된다는 점만 조심해주면 특별할 게 없어보입니다.

 

설계

자 그러면 어떻게 설계에 들어가야 할까요? 

우선 check() 로직부터보면, 뿌요들이 폭파되려면 상하좌우 네개가 연속해서 연결되어 있어야합니다..이걸 어떻게 구현할까요? 

여기서 어렴풋이 dfs, bfs 가 떠오르죠? dfs나 bfs를 한 번 풀어보셨던 분들은 알겠지만 딱 느낌이 오지 않나요?

주인장 같은 경우에는 확신은 안드는데 일단 dfs가 떠올라서 dfs로 구현하려면 어떻게 해야되지? 하고 생각하다가 방향을 잡고 구현을 마친것같아요. 

그리고, 떠오르는 여러 가지 생각들이 있죠?

가령,

dfs돌리는 와중에 스택에 좌표들을 박아놓고 그 좌표의 숫자들을 센 다음에 4 이상이면 기억해놨다가 '.' 으로 바꿔주면 될거같다는 생각이 들어요~ 이런 생각들 간단히 어딘가 메모만 해두고 넘어갑시다! 

 

move()로직은 어떻게 해야할까요?

이건 다들 쉽게 하셨을것같아요~ 주인장 zzino는 한 열 단위로 잡아서 for문 돌면서 .이 나오면 뿌요와 스왑 뿌요가 나오면 continue 형식으로 짰습니다. 2048 easy 를 풀고 난 직후라 조금 비슷한 idea를 떠올려서 거의 똑같이 구현을 했습니다.

지장은 없지만 복잡도가 O(N^2) 이 나오는 로직인데 혹시 O(N)이신분 알고계시면 공유좀 부탁드립니다 ㅎㅎ

 

여기까지 보셨으면 구현은 꼭! 한 번 혼자 해보고 들어가시길 바랍니당 ㅎㅎ

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    static char[][] board = new char[12][12];
    static int count = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 12; i++) board[i] = br.readLine().toCharArray();
        while (check()) {
            move();
            count++;
        }
        System.out.println(count);
    }

    static boolean check() {
        Stack<Point> st = new Stack<>();
        boolean[][] visit = new boolean[12][board[0].length];
        boolean isGood = false;

        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.' && !visit[i][j]) {
                    ArrayList<Point> al = new ArrayList<>();
                    Point start = new Point(i, j);
                    st.push(start);
                    visit[start.x][start.y] = true;
                    while (!st.isEmpty()) {
                        Point prev = st.pop();
                        al.add(prev);
                        for (int k = 0; k < 4; k++) {
                            int xx = prev.x + dx[k];
                            int yy = prev.y + dy[k];
                            if (xx >= 12 || xx < 0 || yy >= board[0].length || yy < 0) continue;
                            if (board[xx][yy] != board[i][j] || visit[xx][yy]) continue;
                            st.push(new Point(xx, yy));
                            visit[xx][yy] = true;
                        }
                    }
                    if (al.size() >= 4) {
                        for (Point p : al) {
                            board[p.x][p.y] = '.';
                        }
                        isGood = true;
                    }
                }
            }
        }
        return isGood;
    }

    static void move() {
        for (int i = 0; i < board[0].length; i++) {
            loop :
            for (int j = 11; j >= 0; j--) {
                if (board[j][i] == '.') {
                    int index = j;
                    while (board[index][i] == '.') {
                        index--;
                        if (0 > index) break loop;
                    }
                    board[j][i] = board[index][i];
                    board[index][i] = '.';
                }
            }
        }
    }

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

눈여겨 볼 점만 소개해드리자면요,

 

1, Line 25

visit 배열을 일부러 밖에 빼놨습니다! 스택은 사실 for문 밖에있으나 안에 있으나 상관이 없는데(while문 조건이 !st.isEmpty() 이므로) visit 배열을 밖에 안 빼놓고 쓰면 사라지는데, 이는 모든 점들에 대해 검사(Line 30)를 하게 만들어 같은 연결 요소가 중복해서 check 되는 불상사가 생길 수 있습니다. 

(사실 dfs 로직이 끝나고 뒤에 if(count >= 4) 에서 '.' 으로 바꿔주기 때문에 신경쓸 필요가 없긴합니다 ^^:;)

 

2, Line 47

처음에 제가 짤 때는 4개이상인 점들을 다 기억하지 않고 첫 점만 기억해놓고 count >= 4면 다시 그점들만 dfs를 돌면서 board의 해당 좌표들을 '.'으로 바꿔줬는데요, 너무 비효율적이고 중복이 생겨 어떻게 해결할까 고민하던 중

dfs로직 와중에 stack에서 pop혹은 push 해줄때마다 arrayList에 뿌요들을 넣어주고, 이때 arrayList의 사이즈가 4이상이라면 상하좌우로 4개이상 연결되 있다는 뜻이므로 좌표들을 '.'으로 바꿔주는 아이디어가 떠올라 구현했습니다.

사실 처음에도 떠오르긴 했었는데 1개 2개 혹은 3개 같이 연속되지않은 뿌요들을 arrayList에 넣어주면 괜히 담은거니까 비효율적이지 않나 그리고 이중for문 바깥에 선언하면 arrayList가 초기화가 되지않아 계속 누적되서 차있는 상태인데 어떻게 쓰지? 하는 생각에 쓰지 않았습니다. 하지만 시간복잡도상 아무 문제도 없고, 코드가 간결해지기 때문에 괜찮다고 볼 수 있습니다.

 

3, Line 66

여기서 index의 의미는 처음 만나는 뿌요의 위치라고 생각하시면 편하게 이해하실 수 있습니다!

 

인사하는 zzino

감사합니다 여러분! 다음 편에서 뵐게요~~