[Baekjoon] 11559_Puyo Puyo

Gold IV

문제(출처: https://www.acmicpc.net/problem/11559)

---

< Puyo Puyo >

 

문제 풀이 

 

필드 바닥부터 bfs 탐색을 통해 같은 색 뿌요가 4개 이상 연결되어 있는 부분을 찾는다.

찾은 부분을 터트린 후 빈 공간으로 만들어준다.

중력을 통해 아래로 떨어지도록 만드는 과정을 반복해 준다.

 

 

 my solution (Java)

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

public class _11559_ { // Puyo Puyo
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static char arr[][];
	static int cnt, result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		arr = new char[12][6];
		boolean[][] visited = new boolean[12][6];
		boolean[][] check = new boolean[12][6];

		for (int i = 0; i < 12; i++) {
			String str = bf.readLine();
			for (int j = 0; j < 6; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		result = 0;
		boolean flag = false;

		while (true) {
			for (int i = 11; i >= 0; i--) {
				for (int j = 0; j < 6; j++) {
					if (arr[i][j] != '.' && !visited[i][j]) {
						bfs(i, j, arr[i][j], visited, check);
						if (cnt >= 4) {
							flag = true;
							boom(check);
						}
						init(check);
					}
				}
			}
			if (!flag) {
				break;
			} else {
				result += 1;
				flag = false;
			}

			init(visited);
			gravity();
		}
		System.out.println(result);
	}

	private static void gravity() {
		for (int i = 0; i < 6; i++) {
			int idx = -1;
			for (int j = 11; j >= 0; j--) {
				if (idx == -1 & arr[j][i] == '.') {
					idx = j;
				} else if (idx != -1 && arr[j][i] != '.') {
					arr[idx][i] = arr[j][i];
					arr[j][i] = '.';
					idx -= 1;
				}
			}
		}
	}

	private static void bfs(int i, int j, char color, boolean visited[][], boolean check[][]) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { i, j });
		visited[i][j] = true;
		check[i][j] = true;
		cnt = 1;

		while (!queue.isEmpty()) {
			int temp[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int x = temp[0] + dx[k];
				int y = temp[1] + dy[k];
				if (x >= 0 && x < 12 && y >= 0 && y < 6 && !visited[x][y] && arr[x][y] == color) {
					visited[x][y] = true;
					check[x][y] = true;
					queue.add(new int[] { x, y });
					cnt += 1;
				}
			}
		}
	}

	private static void boom(boolean[][] check) {
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (check[i][j]) {
					arr[i][j] = '.';
				}
			}
		}
	}

	private static void init(boolean[][] check) {
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				check[i][j] = false;
			}
		}
	}
}

 

Main

변수)
arr : 필드 정보
visited : 전체 필드 탐색 후 방문 여부
check : 같은 색 뿌요 탐색 여부
result : 연쇄 횟수
flag : 연쇄 작용 여부
cnt : 상하좌우 같은 색 뿌요 개수

 

- 필드 정보 입력 후 저장(arr)

- 연쇄 작용이 없을 때까지 반복

: 바닥부터 탐색해서  빈 공간이 아니고 아직 방문하지 않았다면 bfs함수 호출

: bfs 탐색 후 같은 색 뿌요가 4개 이상이라면 boom 함수 호출하여 터트리기

: 같은 색 뿌요 탐색 여부를 판단하는 chek 배열 초기화

: 연쇄작용이 없었다면 종료

: 연쇄작용이 있었다면 연쇄 횟수(result) +1 후 전체 방문 여부(visited) 초기화 및 중력 작용을 위해 gravity 함수 호출

-  정답(result) 출력

 

gravity

- 바닥부터 열끼리 탐색하여 빈 공간이 있다면 뿌요를 내려줌

 

bfs

- 상하좌우 연결된 곳이 같은 뿌요 색이라면 방문 표시 및 queue에 추가, 상하좌우 같은 색 뿌요 개수(cnt) +1

 

boom

- 뿌요를 터트려 빈 공간으로 만듦

 

init

- 방문 여부 초기화

---

---