[백준]11559: Puyo Puyo - JAVA

[백준]11559: Puyo Puyo

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

풀이

BFS알고리즘을 사용하여 문제를 풀었다. BFS + 구현 능력을 보기에 아주 적절한 문제라고 생각했다.

 

코드를 구현할 때는 다음과 같은 순서로 구현해 주었다.

1. 입력받은 필드를 탐색하며 뿌요가 있는 필드에 도달하면 그 근처에 같은 색의 뿌요가 몇개 있는지 BFS 알고리즘을 통해 탐색한다.
2. 같은 색의 뿌요가 4개 이상이라면 해당 뿌요들을 연쇄시킨다.
3. 연쇄가 일어났다면 뿌요들을 아래로 떨어뜨리고 연속연쇄 수를 하나 늘려준다. 연쇄가 일어나지 않았다면 탐색을 종료한다.

 

같은 뿌요들을 탐색할 때 arraylist를 사용하여 같은 색의 뿌요 개수와 위치를 저장한 다음 4개 이상이라면 한번에 처리해 주도록 하였다.

 

이번 문제에서 가장 많이 헤멨던 부분은 뿌요들을 아래로 떨어뜨리는 부분이었다. 아직 수학적 사고력이 부족한가보당.. 뿌요들을 아래로 떨어뜨리는 코드를 설명하자면 아래와 같다.

1. 각각의 열마다 가장 마지막 행 부터 탐색을 시작한다. 현재 위치의 필드 값이 '.'이라면 '.' 위에 뿌요가 존재하는지 확인 후 떨어 뜨려 주어야 하기 때문에 현재 행 보다 위의 행을 탐색한다.
2. 뿌요를 발견하면 현재 위치에 해당 뿌요를 입력하고 해당 뿌요의 위치에는 '.'을 입력해 떨어뜨려 준다.
3. 현재 행의 위치를 한칸 올려주고, 다시 확인하는 과정을 반복한다.

그림으로 설명하자면 아래와 같다.

위의 그림을 기준으로 현재 빨간색 뿌요가 (0,1) (3, 1)에 있다고 해보자.

i가 1이고 j가 4이고 k가 3일때 j,i는 비어있고 k, i 위치에 뿌요가 있으므로 j, i에 뿌요를 입력하여 뿌요를 떨어뜨려 준다.

그 다음 탐색을 진행하다가 i가 1이고 j가 3이고 k가 0이 되었을때 j, i는 비어있고 k,i 위치에 뿌요가 있으므로 j, i에 뿌요를 입력하여 뿌요를 떨어뜨려 준다.

 

이번 문제의 예제 입력에는 없는 몇 가지 테스트 케이스들을 가져와 보았다.

 

1. input:

RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRGG
RRRRRR
RRRRGG
RRRRRR
output: 2

 

2. input:

RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRRRRR
RRBBRR
RRRRRR
RRRRRR
RRRRRR
RRBBRR
RRRRRR
RRRRRR
output: 2

 

코드

import java.util.*;
 
public class Main {
    
    static char[][] board;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static ArrayList<Node> list;
    static int n = 12, m = 6;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        board = new char[n][m];
        for(int i = 0; i < n; i++) {
            String field = scan.nextLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = field.charAt(j); 
            }
        }
        
        int count = 0;
        //board를 탐색하며 4개 이상 뭉쳐있는 노드를 확인한다.
        while(true) {
            boolean isFinished = true;
            visited = new boolean[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    if(board[i][j] != '.') {
                        list = new ArrayList<>();
                        bfs(board[i][j], i, j);
                        
                        if(list.size() >= 4) {
                            isFinished = false; //연쇄가 일어났으므로 더 탐색해보아야 한다.
                            for(int k = 0; k < list.size(); k++) {
                                board[list.get(k).x][list.get(k).y] = '.'; // 터트려서 없앰
                            }
                        }
                    }
                }
            }
            if(isFinished) break;
            fallPuyos(); // 뿌요들을 떨어뜨린다.
            count++;
        }
        System.out.println(count);
    }
    
    public static void fallPuyos() {        
        for (int i = 0; i < m; i++) {
            for (int j = n - 1; j > 0; j--) {
                if (board[j][i] == '.') {
                    for (int k = j - 1; k >= 0; k--) {
                        if (board[k][i] != '.') {
                            board[j][i] = board[k][i];
                            board[k][i] = '.';
                            break;
                        }
                    }
                }
            }
        }
    }
    
    public static void bfs(char c, int x, int y) {
        Queue<Node> q = new LinkedList<>();
        list.add(new Node(x, y));
        q.offer(new Node(x, y));
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < m && visited[nx][ny] == false && board[nx][ny] == c) {
                    visited[nx][ny] = true;
                    list.add(new Node(nx, ny));
                    q.offer(new Node(nx, ny));
                }
            }
        }
    }
 
    public static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}