https://www.acmicpc.net/problem/16768
ํด๋น ๋ฌธ์ ๋ ๊ณผ๊ฑฐ ๋ฟ์๋ฟ์ ๊ฒ์์ pop์กฐ๊ฑด์ ๊ตฌํํ๋ ๋ฌธ์ ์ด๋ค.
๋ฌธ์ ์์๋ K๊ฐ ์ด์์ ๊ฐ์ ์๊ฐ ๋ถ์ด์์ผ๋ฉด ํด๋น ์๋ค์ ์ญ์ ๊ฐ ๋๊ณ ๊ฐ์ ๋ผ์ธ์ ์๋ ์ซ์๋ค์ด ์๋๋ก ๋ด๋ ค์ค๋ ๊ฒฐ๊ณผ๋ฅผ ๋ณด์ฌ์ฃผ๋ฉด ๋๋ค.
ํด๋น ๋ฌธ์ ๋ฅผ ํ๊ธฐ ์ํด์๋ DFS๋ฅผ ์ฌ์ฉํ์ฌ ํ์์ ํ๋ฉฐ ์ฃผ๋ณ์ ๊ฐ์ ์๋ค์ด ๋ช๊ฐ๊ฐ ์๋์ง ํ์ ๋ฐ ํด๋น ์์น๋ค์ ์ ์ฅํ๋ฉฐ ์งํํด์ผํ๋ค.
๋ง์ฝ ํ์์ ํ๋ฉฐ K๊ฐ ์ด์์ ๋ธ๋ก์ด ๋ถ์ด์๋ค๋ฉด ํด๋น block์ 0์ผ๋ก ์์น๋ฅผ ๋ณ๊ฒฝํ ํ ์์ ๋ธ๋ก๋ค์ ๋ด๋ ค์ฃผ๋๋ก method๋ค์ ๊ตฌํํ๋ฉด ๋๋ค.
์ฃผ์ด์ง ํ ์คํธ ์ผ์ด์ค๋ ํต๊ณผํ๋ ํ ์คํธ์์๋ ์คํจ๋ฅผ ํฉ๋๋ค...๋ฐ๋ก๋ฅผ ์๊ณ ์ถ์ต๋๋ค๐ฅ
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static int[][] matrix;
static boolean[][] check;
static ArrayList<Integer> storeX;
static ArrayList<Integer> storeY;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int count;
static int K;
static int N;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
matrix = new int[N][10];
for (int i=0; i<N; i++) {
matrix[i] = Arrays.stream(br.readLine().split("")).mapToInt(Integer::parseInt).toArray();
}
// ์์ด์ง๋๊ฒ ์์ ๋๊น์ง pop!!
boolean flag = true;
while (flag) {
flag = pop();
}
for (int i=0; i<N; i++) {
for (int j=0; j<10; j++) {
bw.write(matrix[i][j]+ " ");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
static boolean pop() {
// ๋ด๋ถ ํ์ํ๋ฉฐ ๊ฐ์ ๊ฒ๋ค popํ๊ธฐ
check = new boolean[N][10];
boolean isPoped = false;
for (int i=0; i<(10*N); i++) {
int r = i/10;
int c = i%10;
// ํด๋น ๊ฐ์ด 0์ด๋ฉด pass
if (matrix[r][c] == 0) continue;
count = 0;
storeX = new ArrayList<>();
storeY = new ArrayList<>();
// dfsํ์์ ํตํด ์ฃผ๋ณ์ ๊ฐ๋ ๊ฐ๋ค์ด ์์นํ x,y๊ฐ๋ค ์ ์ฅ
dfs(r, c);
if (count >= K) {
for (int j=0; j<storeX.size(); j++) {
int rx = storeX.get(j);
int ry = storeY.get(j);
matrix[rx][ry] = 0;
}
isPoped = true;
}
}
if (isPoped) {
// ์นธ ๋ด๋ฆฌ๋ ์ฝ๋ ์ถ๊ฐ
putFloor();
return true;
}
else return false;
}
// dfs๋ฅผ ํตํ ์ฐ๊ฒฐ๋ ๋ถ๋ถ ํ์
static void dfs(int r, int c) {
check[r][c] = true;
storeX.add(r);
storeY.add(c);
count++;
int value = matrix[r][c]; // ํ์ฌ ์์น์ ๊ฐ
for (int i=0; i<4; i++) {
if (0 <= r+dx[i] && r+dx[i] < N && 0 <= c+dy[i] && c+dy[i] < 10) {
if (!check[r+dx[i]][c+dy[i]] && matrix[r+dx[i]][c+dy[i]] == value) {
dfs(r+dx[i], c+dy[i]);
}
}
}
}
static void putFloor() {
for (int i=0; i< 10; i++) {
boolean needChange = false;
int savePosition = N-1;
for (int j=N-1; j>=0; j--) {
if (matrix[j][i]==0) {
needChange = true;
}
if (needChange && matrix[j][i]!=0) {
matrix[savePosition][i] = matrix[j][i];
savePosition--;
matrix[j][i] = 0;
}
}
}
}
}
๊ฐ๋ฐํ๋ ๊ณ ๋ผ๋๋์ ์ฝ๋๋ฅผ ์ฐธ์กฐํ์์ต๋๋ค.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static class Point{
int x, y;
public Point(int y, int x) {
this.x = x;
this.y = y;
}
}
static Stack<Point> stack = new Stack<>();
static int N,K,cnt;
static int[] dy = {-1, 1, 0, 0}, dx = {0, 0, -1, 1};
static int[][] matrix;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
matrix = new int[N+1][11];
for (int i=1; i<=N; i++) {
char[] str = br.readLine().toCharArray();
for(int j=1; j<=10; j++) {
matrix[i][j] = str[j-1] - '0';
}
}
while(true) {
visited = new boolean[N+1][11];
boolean flag = false;
downward();
for (int i=N; i>0; i--) {
for (int j=1; j<=10; j++) {
if (visited[i][j] || matrix[i][j]==0) continue;
stack.clear();
cnt = 0;
DFS(i, j, matrix[i][j]);
if (cnt >= K) {
flag = true;
for (Point p:stack) matrix[p.y][p.x] = 0;
}
}
}
if (!flag) break;
}
StringBuilder sb = new StringBuilder();
for (int i=1; i<=N; i++) {
for (int j=1; j<=10; j++)
sb.append(matrix[i][j]);
sb.append("\n");
}
System.out.println(sb.toString());
}
static void downward() {
for (int i= N-1; i>0; i--) {
for (int j=1; j<=10; j++) {
if (matrix[i][j] == 0 || matrix[i+1][j] != 0) continue;
int z = i+1;
while(z <= N && matrix[z][j] == 0) {
matrix[z][j] = matrix[z-1][j];
matrix[z-1][j] = 0;
z++;
}
}
}
}
static void DFS (int y, int x, int value) {
cnt++;
visited[y][x] = true;
stack.push(new Point(y,x));
for (int a=0; a<4; a++) {
int ny = y+dy[a];
int nx = x+dx[a];
if (ny < 1 || nx < 1 || ny > N || nx > 10 || visited[ny][nx] || matrix[ny][nx]!=value) continue;
DFS(ny, nx, value);
}
}
}