11559번 Puyo Puyo
난이도
골드 5
문제 설명
https://www.acmicpc.net/problem/11559
문제
뿌요뿌요의 룰은 다음과 같다.
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!
입력
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.
출력
현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.
요구사항
이 문제는 12x6 필드에서 '연쇄'가 총 몇 회 발생하는지 계산하는 시뮬레이션 문제이다.
- 상하좌우로 4개 이상 연결된 같은 색 뿌요를 찾는다.
- 터질 수 있는 그룹이면 동시에 모두 터져야 한다.
- 뿌요가 터진 후, 위에 있던 뿌요는 중력에 영향을 받아 아래로 떨어져야 한다.
- 뿌요가 떨어진 후, 위와 같은 조건이 만족하면 연쇄가 발생한다.
접근 방식
'터질 것이 없을 때까지 반복한다.'는 요구사항을 보고, 시뮬레이션 while 루프를 기본 뼈대로 잡았다. 한번의 루프는 '탐색 및 폭발' -> '중력 적용'의 사이클을 반복하도록 접근하였다.
12x6의 필드이므로, 이중 for 루프로 배열을 전체 탐색을 하더라도 O(72)이므로, 시간초과는 크게하지 걱정하지 않았다.
연쇄 반응 처리
가장 고민했던 부분은 "언제 루프를 멈출 것인가?"였다.
int cnt = -1; // 이전 연쇄 횟수 int answer = 0; // 현재 연쇄 횟수 while (cnt != answer) { // 이전 턴과 현재 턴의 연쇄 횟수가 다르면 계속 진행 cnt = answer; // 현재 상태를 '이전 상태'로 백업 search(); // 탐색 및 폭발 (+중력) } System.out.println(answer);search() 함수는 "한 턴에 터질 게 있다면 answer를 1 증가시키고 중력을 적용"하는 역할을 한다. 만약 search()를 실행했는데도 answer 값이 변하지 않았다면(즉, cnt == answer), 더 이상 터질 게 없다는 뜻이므로 루프가 종료되도록 구현하였다.
뿌요 탐색 및 폭발
매 턴마다 이중 for문으로 배열을 순회하였다. boolean[][] visited 배열을 매번 새로 생성하여 방문 여부를 체크하고 if (arr[i][j] != '.' && !visited[i][j]) : 뿌요가 있고 아직 방문 안 한 곳이라면 BFS를 시작하였다.
BFS()는 큐(Queue)를 이용해 상하좌우로 같은 색 뿌요를 탐색하고, List에 터질 후보들을 저장한다.
List의 크기가 4 이상이면, 폭발이 일어나므로 리스트의 모든 좌표를 '.'으로 바꾸고 true를 반환합니다
boolean flag: search() 내부에 flag를 두어, 이번 턴에 단 한 그룹이라도 터졌는지 여부를 기록하여 BFS가 true를 반환하면, answer++를 하고 move()를 호출하여 중력 적용을 하였다.
중력 적용
중력 적용은 열 단위로 처리하는 것이 가장 효율적이라고 생각하였다. 6개의 각 열에 대해 반복하여 뿌요를 가장 아래 행부터 채운 후, 나머지는 '.'으로 채워 간단하게 구현하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Point{
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main{
static char[][] arr;
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, -1, 0, 1};
static int r = 12, c = 6, answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
arr = new char[r][c];
for(int i=0; i < r; i++){
String line = br.readLine();
for(int j=0; j<c; j++){
arr[i][j] = line.charAt(j);
}
}
int cnt = -1;
while (cnt != answer){
cnt = answer;
search();
}
System.out.println(answer);
}
static void move(){
Queue<Character> li = new LinkedList<>();
for(int col = 0; col < c; col++){
for(int row = r-1; row>=0; row--){
if(arr[row][col] != '.'){
li.offer(arr[row][col]);
}
}
int x = r-1;
while (!li.isEmpty()){
arr[x][col] = li.poll();
x--;
}
while (x >= 0){
arr[x][col] = '.';
x--;
}
}
}
static boolean BFS(int x, int y, boolean[][] visited){
char target = arr[x][y];
Queue<Point> q= new LinkedList<>();
List<Point> li = new ArrayList<>();
q.offer(new Point(x, y));
li.add(new Point(x, y));
while (!q.isEmpty()){
Point now = q.poll();
for(int d=0; d<4; d++){
int nx = now.x + dx[d];
int ny = now.y + dy[d];
if(nx<0 || nx>=r || ny<0 || ny>=c) continue;
if(visited[nx][ny]) continue;
if(arr[nx][ny] == target){
visited[nx][ny] = true;
q.offer(new Point(nx, ny));
li.add(new Point(nx, ny));
}
}
}
if(li.size() >= 4){
for(Point p : li){
arr[p.x][p.y] = '.';
}
return true;
}
return false;
}
static void search(){
boolean[][] visited = new boolean[r][c];
boolean flag = false;
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
if(arr[i][j] != '.' && !visited[i][j]){
visited[i][j] = true;
if(BFS(i, j, visited)) flag = true;
}
}
}
if(flag){
answer++;
move();
}
}
}
느낀점
처음 이 문제를 보고, 구현하기 전 간단히 어떻게 구현해야할지 고민하는 중 반복문과 함수 호출이 많아 비효율적일까 걱정하였다. 하지만, H=12, W=6으로 크기가 고정되어 있어 과감하게 완전 탐색을 시도하는 것이 중요하다고 느꼈다.
초반에, 연쇄가 발생하지 않을 때까지 반복하는 작업과 4개 이상 인접한 뿌요를 찾는 작업, 폭발 및 중력 적용 작업을 한번에 해결하려고 생각하니 매우 답답하였다. 하지만, 시뮬레이션 문제는 전체 규칙을 한번에 적용하지 말고 규칙을 작게 나누어 문제를 해결하는 것이 중요하다고 생각되었다.
마지막으로, 자바의 Pass-by-value를 다시 상기시킬 수 있었다. 처음에는, 규칙을 구현하는데 집중하여 BFS(..., boolean flag)를 넘겨서 BFS 내부에서 serach() 내 flag의 값을 변경하려고 시도하였다. 하지만, 당연히 그 값은 변하지 않았고 문제점을 파악하여 코드를 수정할 수 있었다. 자바는 기본형을 넘길 때 값을 복사해서 넘긴다는 것을 다시 상기시킬 수 있었다.
