[BOJ/Java] Puyo Puyo (11559)

Puyo Puyo (11559)

1. 문제 분석

문제 개요

• 6x12 크기의 필드에서 같은 색의 뿌요(Puyo)가 4개 이상 연결되면 터지고, 터진 후에는 위의 뿌요들이 아래로 떨어진다. 더 이상 터질 수 있는 뿌요가 없을 때까지 반복하고, 이때 발생하는 연쇄의 횟수를 구하는 문제이다.

입력 형식

• 12개의 줄에 각각 6개의 문자로 이루어진 필드의 상태가 주어진다. 필드는 ".", "R", "G", "B", "P", "Y"로 이루어지며, 각각 빈 공간과 다섯 가지 색상의 뿌요를 나타낸다.

출력 형식

• 터질 수 있는 모든 뿌요가 터진 후 발생한 연쇄의 횟수를 출력한다.

2. 알고리즘 종류

• DFS(깊이 우선 탐색) 알고리즘을 사용하여 필드의 각 위치에서 같은 색의 뿌요가 몇 개 연결되어 있는지를 확인한다.
• Stack(스택) 자료구조를 사용하여 뿌요가 터진 후 남은 뿌요들을 아래로 떨어뜨리는 과정을 구현한다.

3. 주요 부분 및 코드 작성 방법

1. DFS(깊이 우선 탐색) 사용

• DFS를 사용하여 현재 위치에서 시작해 상하좌우로 같은 색의 뿌요가 몇 개 연결되어 있는지 탐색하고, 4개 이상이면 해당 뿌요들을 터뜨린다.

2. 연쇄 반응 확인

• 한 번의 탐색(DFS)이 끝나면 필드를 확인하여 뿌요들이 터졌는지 여부를 확인하고, 터진 경우 연쇄 반응 횟수를 증가시킨다.

3. 뿌요가 터진 후 아래로 떨어뜨리기

• 뿌요가 터진 후 남은 뿌요들이 아래로 떨어질 수 있도록 필드를 갱신한다. 이를 위해 스택 자료구조를 사용해 필드를 아래에서 위로 스캔하면서 빈 공간을 채운다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 배열 초기화
  • 필드의 상태를 입력받고 배열을 초기화한다.
• for (int i = 0; i < R; i++) { field[i] = br.readLine().split(""); // 필드 상태 입력 }
• DFS를 통한 뿌요 터뜨리기 및 연쇄 횟수 계산
  • 모든 뿌요가 터질 때까지 연쇄 반응을 반복하고, 연쇄 횟수를 계산한다.
• int answer = 0; boolean flag = true; while (flag) { visited = new boolean[R][C]; // 방문 기록 초기화 flag = false; for (int i = R - 1; i >= 0; i--) { // 아래에서부터 탐색 시작 for (int j = 0; j < C; j++) { if (field[i][j].equals(".")) continue; // 빈 공간은 건너뜀 point = new ArrayList<>(); // 터질 뿌요의 위치를 저장할 리스트 초기화 if (dfs(i, j, field[i][j]) >= 4) { // 뿌요가 4개 이상 연결된 경우 for (Point p : point) field[p.x][p.y] = "."; // 해당 뿌요를 터뜨림 flag = true; // 연쇄 반응 발생 } } } if (flag) { answer++; // 연쇄 횟수 증가 down(); // 남은 뿌요를 아래로 떨어뜨림 } } System.out.println(answer); // 연쇄 횟수 출력

(2) DFS 함수 (dfs)

• 초기화 및 방문 기록
  • 현재 위치와 연결된 뿌요의 개수를 기록한다.
• visited[r][c] = true; // 현재 위치 방문 처리 point.add(new Point(r, c)); // 현재 위치를 터질 뿌요 목록에 추가 int cnt = 1; // 연결된 뿌요의 개수 초기화
• 4방향 탐색 및 연결된 뿌요 개수 갱신
  • 4방향으로 이동하며 연결된 같은 색 뿌요의 개수를 계산한다.
• for (int i = 0; i < 4; i++) { // 상하좌우 탐색 int nr = r + dr[i]; int nc = c + dc[i]; if (nr < 0 || nc < 0 || nr >= R || nc >= C || visited[nr][nc] || !field[nr][nc].equals(color)) continue; // 경계 조건 및 방문 여부 확인 cnt += dfs(nr, nc, color); // 재귀 호출을 통해 연결된 뿌요 개수 갱신 } return cnt; // 최종 연결된 뿌요 개수 반환

(3) 뿌요 아래로 떨어뜨리기 함수 (down)

• 스택을 이용한 필드 갱신
  • 스택을 사용해 필드의 각 열을 아래에서 위로 스캔하며 남은 뿌요들을 아래로 떨어뜨린다.
• for (int i = 0; i < C; i++) { // 열 단위로 스캔 Stack<String> stack = new Stack<>(); for (int j = 0; j < R; j++) { if (!field[j][i].equals(".")) { // 빈 공간이 아니면 스택에 추가 stack.push(field[j][i]); field[j][i] = "."; // 현재 위치를 빈 공간으로 갱신 } } int cnt = R - 1; // 아래에서부터 뿌요를 채움 while (!stack.isEmpty()) { field[cnt--][i] = stack.pop(); // 스택에서 꺼낸 뿌요를 아래부터 채움 } }

5. 전체 코드

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class BOJ11559 {
    static int R = 12, C = 6; // 필드의 행과 열 크기
    static String[][] field = new String[R][C]; // 필드 상태를 저장하는 배열
    static boolean[][] visited; // 방문 여부를 기록하는 배열
    static List<Point> point; // 터질 뿌요의 위치를 저장하는 리스트
    static int[] dr = {-1, 1, 0, 0}; // 상하좌우 이동을 위한 행 변화량
    static int[] dc = {0, 0, -1, 1}; // 상하좌우 이동을 위한 열 변화량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        for (int i = 0; i < R; i++) {
            field[i] = br.readLine().split(""); // 필드 상태 입력
        }

        int answer = 0; // 연쇄 횟수를 저장하는 변수 초기화
        boolean flag = true; // 연쇄 발생 여부를 확인하는 변수 초기화
        while (flag) {
            visited = new boolean[R][C]; // 방문 기록 초기화
            flag = false; // 연쇄 발생 여부 초기화
            for (int i = R - 1; i >= 0; i--) { // 필드의 아래쪽부터 탐색 시작
                for (int j = 0; j < C; j++) {
                    if (field[i][j].equals(".")) continue; // 빈 공간은 건너뜀
                    point = new ArrayList<>(); // 터질 뿌요의 위치를 저장할 리스트 초기화
                    if (dfs(i, j, field[i][j]) >= 4) { // 4개 이상의 뿌요가 연결된 경우
                        for (Point p : point) field[p.x][p.y] = "."; // 해당 뿌요를 터뜨림
                        flag = true; // 연쇄 발생 여부 설정
                    }
                }
            }
            if (flag) { // 연쇄가 발생한 경우
                answer++; // 연쇄 횟수 증가
                down(); // 뿌요가 터진 후 남은 뿌요를 아래로 떨어뜨림
            }
        }
        System.out.println(answer); // 최종 연쇄 횟수 출력
    }

    // DFS를 이용해 연결된 뿌요의 개수를 세는 함수
    public static int dfs(int r, int c, String color) {
        visited[r][c] = true; // 현재 위치 방문 처리
        point.add(new Point(r, c)); // 현재 위치를 터질 뿌요 목록에 추가
        int cnt = 1; // 현재 위치 포함 1개로 시작

        // 상하좌우 4방향으로 탐색
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || visited[nr][nc] || !field[nr][nc].equals(color)) continue; // 경계 조건 및 방문 여부 확인
            cnt += dfs(nr, nc, color); // 재귀 호출을 통해 연결된 뿌요 개수 갱신
        }
        return cnt; // 최종 연결된 뿌요 개수 반환
    }

    // 뿌요가 터진 후 남은 뿌요들을 아래로 떨어뜨리는 함수
    public static void down() {
        for (int i = 0; i < C; i++) { // 열 단위로 탐색
            Stack<String> stack = new Stack<>(); // 뿌요들을 담을 스택 생성
            for (int j = 0; j < R; j++) {
                if (!field[j][i].equals(".")) { // 빈 공간이 아닌 경우 스택에 추가
                    stack.push(field[j][i]);
                    field[j][i] = "."; // 현재 위치를 빈 공간으로 갱신
                }
            }
            int cnt = R - 1; // 아래에서부터 뿌요를 채움
            while (!stack.isEmpty()) {
                field[cnt--][i] = stack.pop(); // 스택에서 꺼낸 뿌요를 아래부터 채움
            }
        }
    }
}

BFS 풀이

https://moonsbeen.tistory.com/213