11559번: Puyo Puyo
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
www.acmicpc.net
같은 색 뿌요가 4개이상 상하좌우 4방향으로 연결되어있으면 터집니다.
뿌요들이 없어지고나서 남은 뿌요들은 아래로 모두 이동시켜줍니다.
그렇게 모인 뿌요들 중 같은 색 뿌요가 4개이상 모이게 되면 다시 터집니다. => 연쇄가 추가됩니다.
이 과정을 뿌요가 터지지 않을때까지 반복하여 몇 연쇄가 일어나는지 출력하는 문제입니다.
저의 로직은 다음과 같습니다.
1. 12 * 6 배열을 돌면서 뿌요가 있는 칸이면 bfs로 몇개가 모여있는지 확인
2. 4개이상 모여있으면 모여있는 뿌요들 제거 => 이 때 제거할 뿌요는 ArrayList에 넣었습니다.
3. 제거된 뿌요가 없으면 t - 1를 출력 후 리턴하고 아니면 다음으로 넘어갑니다.
4. 제거된 뿌요로 인해 빈칸을 위의 뿌요들로 채워줍니다. (뿌요들을 아래로 내려줍니다.)
3번에서 t - 1을 출력하는 이유는 몇 번 연쇄인지 출력하는 문제인데 t번 턴에서 뿌요가 터지지 않았기 때문입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static char list[][] = new char[12][6];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static ArrayList<int[]> erasepoint = new ArrayList<>();
static boolean visit[][] = new boolean[12][6];
static int cnt;
static void bfs(int sx, int sy) {
Deque<int[]> dq = new ArrayDeque<>();
dq.add(new int[] { sx, sy });
visit[sx][sy] = true;
cnt = 0;
while (!dq.isEmpty()) {
int x = dq.peek()[0];
int y = dq.poll()[1];
erasepoint.add(new int[] { x, y });
cnt++;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6)
continue;
if (visit[nx][ny] || list[nx][ny] != list[x][y])
continue;
dq.add(new int[] { nx, ny });
visit[nx][ny] = true;
}
}
}
static void func() {
for (int t = 1;; t++) {
boolean chk = false;
for (int i = 0; i < 12; i++)
Arrays.fill(visit[i], false);
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 6; j++) {
if (list[i][j] == '.')
continue;
bfs(i, j);
if (cnt >= 4) {
chk = true;
for (int xy[] : erasepoint) {
list[xy[0]][xy[1]] = '.';
}
}
erasepoint.clear();
}
}
if (!chk) {
System.out.println(t - 1);
return;
}
for (int i = 10; i >= 0; i--) {
for (int j = 0; j < 6; j++) {
if (list[i][j] == '.')
continue;
for (int k = i + 1; k < 12; k++) {
if (list[k][j] != '.') {
char tmp = list[i][j];
list[i][j] = list[k - 1][j];
list[k - 1][j] = tmp;
break;
} else {
if (k == 11) {
char tmp = list[i][j];
list[i][j] = list[k][j];
list[k][j] = tmp;
break;
}
}
}
}
}
}
}
static void input() throws Exception {
for (int i = 0; i < 12; i++) {
st = new StringTokenizer(br.readLine());
list[i] = st.nextToken().toCharArray();
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > bfs' 카테고리의 다른 글
| boj 1600 말이 되고픈 원숭이 (0) | 2021.03.24 |
|---|---|
| boj 2589 보물섬 (0) | 2021.03.16 |
| boj 15653 구슬 탈출 4 (0) | 2021.02.22 |
| boj 1525 퍼즐 (0) | 2021.02.19 |
| boj 7576 토마토 (0) | 2021.02.19 |