[백준BOJ] 11559번 Puyo Puyo.java

 

백준 저지에서 puyo puyo를 자바를 통해 풀어 보았다. 

 

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

11559번: Puyo Puyo

11559번 Puyo Puyo.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

11559번 Puyo Puyo

문제

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

설명

호흡이 꽤 긴 문제이다. 사용해야하는 알고리즘은 bfs밖에 없지만 각 기능을 함수로 나누고 순서를 똑바로 하지 않으면 틀릴 위험이 크다. 

 

연쇄가 발동하기 위해서는 같은 색이 4개 이상 붙어있어야 한다. 단 4개 이상 붙어있는게 여러 개 있더라도 한 번의 연쇄이다. 따라서 1번의 연쇄동안 4개 이상 붙어 있는 게 여러 개 있을 경우를 고려한다. 이를 위해 한 번의 연쇄마다 visit을 새로 생성한다. 

 

붙어있는지 여부는 bfs를 통해 확인한다. bfs를 수행할 때 visit을 미리 복사해놓는다. 붙어 있는 색이 4개 미만이라면 복사해놓은 visit을 반환하고 4개 이상이라면 bfs를 통해 수정된 visit을 반환한다. 

 

반환된 visit을 통해 뿌요뿌요가 터지는지를 알 수 있다. 만약 터진다면 터짐과 내려가기를 해야한다. 그리고 다음 연쇄를 위해 재귀함수를 만든다.

 

만약 더 이상 터질 뿌요뿌요가 없다면 현재까지 수행된 연쇄 횟수를 출력하고 함수를 종료한다.

코드

//11559번 Puyo Puyo.java
package boj20211224;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Puyo_Puyo_11559 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class point{
    	int x;
    	int y;
    	point(int x, int y){
    		this.x=x;
    		this.y=y;
    	}
    }
    
	public static void main(String[] args) throws IOException {
		String[][] field = new String[12][6];
		for(int i=0;i<12;i++) {
			String line = br.readLine();
			for(int j=0;j<6;j++) {
				field[i][j] = line.substring(j,j+1);
			}
		}
		game(field, 0);
	}
	
	static void game(String[][] field, int count) {
		boolean[][] visit = new boolean[12][6];
		boolean check = false;
		//삭제되는 뿌요뿌요 확인
		for(int i=0;i<12;i++) {
			for(int j=0;j<6;j++) {
				if(!field[i][j].equals(".") && !visit[i][j]) {
					visit = bfs(field, visit, i, j);
				}
				if(!check && visit[i][j]) {
					check = true;
				}
			}
		}
		
		//뿌요뿌요 터짐 + 내려오기
		if(check) {
			//터짐+내려오기
			field=boomDown(visit, field);
			//다음 연쇄 시작
			game(field, count+1);
		}
		//더 이상 터질 뿌요 없음 -> 연쇄 종료
		else {
			System.out.println(count);
			return;
		}
		
	}
	
	static boolean[][] bfs(String[][] field, boolean[][] visit, int i, int j) {
		int[] di = {1,-1,0,0};
		int[] dj = {0,0,1,-1};
		
		boolean[][] visitCopy = new boolean[12][6];
		for(int x=0;x<12;x++) {
			for(int y=0;y<6;y++) {
				visitCopy[x][y] = visit[x][y];
			}
		}
		
		int count=0;
		String color = field[i][j];
		visit[i][j]=true;
		Queue<point> q = new LinkedList<point>(); 
		q.add(new point(i,j));
		
		while(!q.isEmpty()) {
			point now = q.poll();
			count++;
			for(int d=0;d<4;d++) {
				int nextI = now.x+di[d];
				int nextJ = now.y+dj[d];
				if(0<=nextI&&nextI<12&&0<=nextJ&&nextJ<6) {
					if(field[nextI][nextJ].equals(color) && !visit[nextI][nextJ]) {
						visit[nextI][nextJ] = true;
						q.add(new point(nextI, nextJ));
					}
				}
			}
		}
		if(count<4) {
			visit = visitCopy;
		}
		return visit;
	}
	
	static String[][] boomDown(boolean[][] visit, String[][] field) {
		for(int i=0;i<12;i++) {
			for(int j=0;j<6;j++) {
				if(visit[i][j]) {
					field[i][j]=".";
				}
			}
		}
		
		for(int j=0;j<6;j++) {
			for(int i=11;i>=0;i--) {
				if(!".".equals(field[i][j])) {
					while(i+1<12 && field[i+1][j].equals(".")) {
						field[i+1][j]=field[i][j];
						field[i][j]=".";
						i++;
					}
				}
			}
		}
		return field;
	}
}