Puyo Puyo

문제

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

풀이

이 문제에서 고전했던 부분들은 다음과 같다.

• 그룹마다의 연쇄를 카운팅하는 것이 아니라 연쇄가 발생하는 경우를 카운팅하는 것이다.
• 연쇄가 발생하는 경우를 카운팅하는 것이기 떄문에 같은 턴에서 서로 다른 그룹의 연쇄는 독립적이다.(서로 영향을 주지 않는다)

위 조건들에 따라 로직을 다음과 같은 흐름으로 구성하였다.

1. 입력을 받을 때 좌표를 저장하는 클래스 Node 를 통해 뿌요들의 좌표를 저장한다.
2. 매 턴마다 뿌요들중 연쇄가 가능한 것들이 있는지 확인한다. puyoCount 로직이 코드에서 이를 실행하며 bfs로 같은 색깔의 뿌요들을 상하좌우로 이동하며 탐색해 카운팅하여 반환한다.
3. 앞선 과정에서 반환 값이 4이상인 경우 연쇄가 가능한 경우로 연쇄는 puyo 로직을 통해 수행된다.
4. 반복문 안에서의 result 변수는 연쇄가 발생했는 지를 체크하는 변수로 이 값이 0이면 더 이상 연쇄가 발생한 뿌요가 존재하지 않으므로 반복문을 벗어난다.
5. 연쇄 가능 확인 - 연쇄 과정을 모두 수행하면 gravity 로직을 통해 위 쪽의 뿌요들을 빈 자리까지 끌어내리는 작업을 실행한다.
6. 턴제로 결과를 카운팅하기 위해 while 문을 활용하였으며 뿌요가 아예 존재하지 않는 경우도 빠르게 처리한다.

로직의 시간복잡도는 정확히 추산하기 어려우나, 모든 로직이 $12 \times 6$ 형태의 배열을 탐색하는 형태이므로 사실상 상수 시간에 수렴한다. 따라서 제한 조건 1초를 무난히 통과할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class Main {

  static int[] dr = {-1, 1, 0, 0};
  static int[] dc = {0, 0, -1, 1};
  static char[][] field = new char[12][6];
  static boolean[][] visited = new boolean[12][6];

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    List<Node> colorPoints = new ArrayList<>();

    for (int r = 0; r < 12; r++) {
      String line = br.readLine();
      for (int c = 0; c < 6; c++) {
        field[r][c] = line.charAt(c);

        if (field[r][c] == '.') {
          continue;
        }

        colorPoints.add(new Node(r, c));
      }
    }

    int answer = 0;
    while (!colorPoints.isEmpty()) {
      int result = 0;

      for (Node colorPoint : colorPoints) {
        int sr = colorPoint.r;
        int sc = colorPoint.c;

        if (isNotValidIdx(sr, sc)) {
          continue;
        }

        if (field[sr][sc] == '.') {
          continue;
        }

        initVisited();
        int puyoCount = puyoCount(sr, sc, field[sr][sc]);
        if (puyoCount < 4) {
          continue;
        }

        puyo(sr, sc, field[sr][sc]);
        result++;
      }

      if (result == 0) {
        break;
      }
      answer++;
      gravity();
    }

    System.out.println(answer);
    br.close();
  }

  static void initVisited() {
    for (boolean[] line : visited) {
      Arrays.fill(line, false);
    }
  }

  static boolean isNotValidIdx(int r, int c) {
    return r < 0 || r >= 12 || c < 0 || c >= 6;
  }

  static int puyoCount(int sr, int sc, char color) {
    Queue<Node> queue = new ArrayDeque<>();
    visited[sr][sc] = true;
    queue.offer(new Node(sr, sc));
    int count = 1;

    while (!queue.isEmpty()) {
      Node cur = queue.poll();

      for (int i = 0; i < dr.length; i++) {
        int nr = cur.r + dr[i];
        int nc = cur.c + dc[i];

        if (isNotValidIdx(nr, nc)) {
          continue;
        }

        if (field[nr][nc] != color || visited[nr][nc]) {
          continue;
        }

        visited[nr][nc] = true;
        count++;
        queue.offer(new Node(nr, nc));
      }
    }

    return count;
  }

  static void puyo(int r, int c, char color) {
    Queue<Node> queue = new ArrayDeque<>();
    queue.offer(new Node(r, c));

    while (!queue.isEmpty()) {
      Node cur = queue.poll();

      field[cur.r][cur.c] = '.';

      for (int i = 0; i < dr.length; i++) {
        int nr = cur.r + dr[i];
        int nc = cur.c + dc[i];

        if (isNotValidIdx(nr, nc)) {
          continue;
        }

        if (field[nr][nc] != color) {
          continue;
        }

        queue.offer(new Node(nr, nc));
      }
    }
  }

  static void gravity() {
    for (int r = 10; r >= 0; r--) {
      for (int c = 0; c < 6; c++) {
        if (field[r][c] == '.') {
          continue;
        }

        char color = field[r][c];
        int downRow = r;

        while (downRow + 1 < 12 && field[downRow + 1][c] == '.') {
          downRow++;
        }

        field[r][c] = '.';
        field[downRow][c] = color;
      }
    }
  }

  static class Node {

    int r, c;

    public Node(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }
}

결과