썸네일은 이 문제와 관계가 없을 것입니다.
🔗 링크
https://www.acmicpc.net/problem/11559
✏️ 문제
뿌요뿌요 게임의 필드 상황이 주어졌을 때 몇 번의 연쇄가 발생하는지 구하는 문제입니다.
뿌요가 터지는 조건은 아래와 같습니다.
- 같은 색의 뿌요가 상, 하, 좌, 우로 4개 이상 연결되어 있으면 한꺼번에 터진다. (연쇄 시작, 1연쇄)
- 뿌요가 사라진 빈 공간 위에 뿌요가 있다면 바닥으로 떨어진다.
- 뿌요가 떨어져 재배치되었을 때 1의 조건을 만족한다면 한꺼번에 터지며, 1연쇄를 추가한다.
🧠 접근
자칫 어려워보일 수 있으나 지문에서 제시하는 대로 시뮬레이션하면 되는 문제입니다.
뿌요가 터지는 조건을 만족하는지 어떻게 확인할까?
깊이 우선 탐색으로 간단히 접근할 수 있습니다.
우선 필드를 표현하는 배열의 복사본을 준비합니다. 배열 중 하나는 터질 뿌요를 찾는 데 쓰이며, 다른 하나는 실제 결과물에 반영하기 위해 쓰입니다.
비어 있지 않은 칸을 발견하면 깊이 우선 탐색으로 들어가며, 해당 뿌요의 위치로부터 몇 개의 뿌요가 붙어 있는지 확인합니다.
연결되어 있는 뿌요의 개수를 세기 위해 배열의 복사본을 사용합니다. 중복 계산으로 인한 무한 루프를 막기 위해 체크한 칸은 뿌요 없음으로 바꾸며, 조건을 만족하는 위치를 큐에 추가합니다.
(...main)
do {
// 필드를 순회해 터질 뿌요를 찾음
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 6; j++) {
if (!map[i][j].equals(".")) {
temp = 0;
dfs(i, j, map);
if (temp >= 4) {
explodedPoint.add(new Point(i, j));
isExploded = true;
}
}
}
}
// 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
if (isExploded)
currentRen += 1;
(...)
} while (isExploded);
System.out.println(currentRen);
}
private static void dfs(int x, int y, String[][] map) {
String current = map[x][y];
map[x][y] = ".";
temp += 1;
for (int i = 0; i < 4; i++) {
int nextX = x + DX[i];
int nextY = y + DY[i];
if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6)
continue;
if (map[nextX][nextY].equals(current))
dfs(nextX, nextY, map);
}
}dfs()가 지나온 곳을 빈 곳으로 만들도록 작성되어 있으므로 실제 배열에서 뿌요를 터뜨리는 데도 사용할 수 있습니다.
뿌요를 터뜨리자!
// 터질 뿌요가 없을 때까지 반복
do {
Queue<Point> explodedPoint = new LinkedList<>(); // 터질 뿌요의 시작점을 저장
isExploded = false;
// 필드를 순회해 터질 뿌요를 찾음
(...)
// 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
if (isExploded)
currentRen += 1;
// 실제 반영될 필드에서 뿌요를 터뜨림
while (!explodedPoint.isEmpty()) {
Point p = explodedPoint.poll();
dfs(p.x, p.y, mapBak);
}
(...)
} while (isExploded);터질 뿌요의 정보를 큐에 넣어 두었으므로 간단하게 터뜨릴 수 있습니다. 그러나 터뜨린 직후에는 뿌요가 공중에 떠 있게 되므로 이를 바닥으로 떨어트려 주어야 합니다.
뿌요를 바닥으로 어떻게 떨어트리지?
공중에 떠 있는 뿌요를 어떻게 떨어트릴 수 있을까요? 이 질문에 대해 답을 내기 전에, 뿌요가 떨어지는 조건에 대해 생각해 봅시다.
가령, 아래와 같은 예제가 있다고 합시다. (실제로 가능한 형태가 아닐 수 있습니다.)
......
......
......
......
......
......
......
BY....
BY....
RRG...
RRYG..
BBYGG.이 예제에서 1연쇄가 일어나면 아래와 같이 변합니다.
......
......
......
......
......
......
......
BY....
BY....
..G...
..YG..
BBYGG.여기서 2열을 주목합시다.
.......YY..B
중력에 의해 뿌요가 떨어진다면 빈 칸을 없애기만 하면 됩니다.
필자는 빈 칸을 없애기 위해 .을 제외한 모든 배열의 열 요소를 스택에 집어 넣고 바닥부터 pop하는 방법을 사용하였습니다.
구현하는 방법은 이외에도 여러 가지가 있으니 편한 방법으로 하시면 됩니다.
// 터질 뿌요가 없을 때까지 반복
do {
(...)
// 뿌요를 내려 필드를 다시 그림
for (int i = 0; i < 6; i++) {
Stack<String> verticalPuyos = new Stack<>();
for (int j = 0; j < 12; j++) {
if (!mapBak[j][i].equals("."))
verticalPuyos.add(mapBak[j][i]);
}
int index = 11;
while(!verticalPuyos.isEmpty()) {
mapBak[index][i] = verticalPuyos.pop();
index -= 1;
}
for (int j = index; j >= 0; j--) {
mapBak[j][i] = ".";
}
}
} while (isExploded);이제 currentRen을 출력해 주기만 하면 됩니다!
📄 전체 소스 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;
public class Main {
private static int[] DX = {1, -1, 0, 0};
private static int[] DY = {0, 0, 1, -1};
private static String[][] map, mapBak;
private static int temp;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
boolean isExploded = false; // 각 스캔에서 터졌는지 체크
int currentRen = 0; // 연쇄 횟수
map = new String[12][6];
mapBak = new String[12][6];
for (int i = 0; i < 12; i++)
map[i] = reader.readLine().split("");
copyArray(map, mapBak); // 원본 배열의 백업
do {
Queue<Point> explodedPoint = new LinkedList<>(); // 터질 뿌요의 시작점을 저장
isExploded = false;
// 필드를 순회해 터질 뿌요를 찾음
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 6; j++) {
if (!map[i][j].equals(".")) {
temp = 0;
dfs(i, j, map);
if (temp >= 4) {
explodedPoint.add(new Point(i, j));
isExploded = true;
}
}
}
}
// 터진 뿌요가 하나 이상이면 연쇄 횟수 증가
if (isExploded)
currentRen += 1;
// 실제 반영될 필드에서 뿌요를 터뜨림
while (!explodedPoint.isEmpty()) {
Point p = explodedPoint.poll();
dfs(p.x, p.y, mapBak);
}
// 뿌요를 내려 필드를 다시 그림
for (int i = 0; i < 6; i++) {
Stack<String> verticalPuyos = new Stack<>();
for (int j = 0; j < 12; j++) {
if (!mapBak[j][i].equals("."))
verticalPuyos.add(mapBak[j][i]);
}
int index = 11;
while(!verticalPuyos.isEmpty()) {
mapBak[index][i] = verticalPuyos.pop();
index -= 1;
}
for (int j = index; j >= 0; j--) {
mapBak[j][i] = ".";
}
}
copyArray(mapBak, map);
} while (isExploded);
System.out.println(currentRen);
}
// 2차원 배열 복사
private static void copyArray(String[][] source, String[][] destination) {
for (int i = 0; i < source.length; i++)
System.arraycopy(source[i], 0, destination[i], 0, source[0].length);
}
private static void dfs(int x, int y, String[][] map) {
String current = map[x][y];
map[x][y] = ".";
temp += 1;
for (int i = 0; i < 4; i++) {
int nextX = x + DX[i];
int nextY = y + DY[i];
if (nextX < 0 || nextY < 0 || nextX >= 12 || nextY >= 6)
continue;
if (map[nextX][nextY].equals(current))
dfs(nextX, nextY, map);
}
}
}
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}😉 이 문제를 푸는 데 도움이 된 문제
사진찍는 주니어 프론트엔드 개발자