[백준 11559] Puyo Puyo(뿌요뿌요) (자바)

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

11559번: Puyo Puyo

 

난이도 : 골드 5

 

개인적으로 이런 유형의 문제를 좋아해서 재밌게 풀었습니다.

여러 기능을 구현하다 보면 열심히 일 하는 느낌(?)이 들어서 기분이 좋아요.

다양한 기능이 필요하지만 어렵지 않고 각 기능만 제대로 구현한다면 잘 동작하는 문제였습니다.

한 사이클에 터질 수 있는 블록을 모두 체크해두고 사이클이 끝나면 그 블록들을 터트린 후 

위에 붕 떠있는 블록들을 밑으로 내려주는 과정을 반복하면 됩니다.

쉽죠?

---

전역 변수 

map[][] = 게임판

answer = 몇 사이클 돌았나?(답)

dx [], dy [] = BFS 단골 상, 하, 좌, 우 탐색을 위한 배열

visit [][] = 한 사이클이 끝나고 동시에 블록을 터트려야 하므로 방문을 체크해 줄 배열

list = 터질 블럭의 좌표값을 가지는 리스트

메소드

void main 

입력을 받고 답을 출력합니다.(searchGroup 호출)

void searchGroup

블록은 4개 이상이 붙어있어야 터질 수 있습니다. 

map을 순회하다가 '.'이 아닌 칸(블록이 있는 칸)을 만난다면 grouping메소드를 호출하여

블록들을 연결(list에 add) 블록이 4개가 붙어있는지 확인해줍니다.

블록이 4개 붙어있다면 boom메소드로 터트려줍니다.

그리고 붕 떠있는 블록을 밑으로 내려준 후에 사이클을 1 증가시킵니다.

(grouping, boom, set 호출)

void grouping

파라미터로 받은 좌표(x, y)와 값(c)을 통해 현재 좌표값의 상, 하, 좌, 우를 탐색합니다.

만약 같은 블록이라면 list에 추가해줍니다. dfs로 같은 블록을 모두 찾아냅니다.

(check 호출)

void boom

list의 size가 4 이상일 때 호출됩니다. 현재 list에 저장된 값들은 모두 같은 블록이므로 

모두 터트려줍니다.('.')

void set

붕 떠있는 블록들을 밑으로 내려서 정리시켜주는 메소드입니다. 

y축의 개수(6)만큼 반복하여 한 줄씩 밑으로 내려줍니다.

LinkedList를 이용하여 밑에서부터 '.'이 아닌 블록을 모두 add 했고

한 줄을 탐색하며 '.'으로 채우고 탐색이 끝났을 때 밑에서부터 ll의 값을 채워줬습니다.

boolean check

좌표값이 유효한 값인지 알려줍니다.

class Point

좌표값을 가지는 클래스입니다.

x, y를 저장할 수 있습니다.

 

import java.util.*;
import java.io.*;

public class p11559 {
	static final int X = 12, Y = 6;
	static char map[][] = new char[X][Y];
	static int answer;
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static boolean visit[][];
	static LinkedList<Point> list = new LinkedList<Point>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		answer = 0;

		for(int i = 0; i < 12; i++) {
			String s = br.readLine();
			for(int j = 0; j < 6; j++)
				map[i][j] = s.charAt(j);
		}
		
		searchGroup();
		System.out.println(answer-1);
	}

	public static void searchGroup() {
		boolean finish = false;

		while(!finish) {
			finish = true;
			visit = new boolean[X][Y];
			for(int i = 0; i < X; i++) {
				for(int j = 0; j < Y; j++) {
					if(map[i][j] != '.') {
						list.clear();
						visit[i][j] = true;
						list.add(new Point(i,j));
						grouping(i, j, map[i][j]);
						if(list.size() >= 4) {
							boom();
							finish = false;
						}
					}
				}
			}
			set();
			answer ++;
		}
	}

	public static void grouping(int x, int y, char c) {
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(check(nx, ny) && !visit[nx][ny]) {
				if(map[nx][ny] == c) {
					visit[nx][ny] = true;
					list.add(new Point(nx,ny));
					grouping(nx, ny, c);
				}
			}
		}
	}

	public static void boom() {
		for(int i = 0; i < list.size(); i++) {
			Point p = list.get(i);
			map[p.x][p.y] = '.';
		}
	}

	public static void set() {
		LinkedList<Character> ll = new LinkedList<Character>();
		for(int j = 0; j < Y; j++) {
			ll.clear();
			for(int i = X-1; i >= 0; i--) {
				if(map[i][j] != '.') {
					ll.add(map[i][j]);
					map[i][j] = '.';
				}
			}
			
			for(int i = 0; i < ll.size(); i++) {
				map[X-1-i][j] = ll.get(i);
			}
		}
	}

	public static boolean check(int x, int y) {
		return x >= 0 && y >= 0 && x < X && y < Y;
	}

	static class Point{
		int x, y;
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

재밌죠?