반응형
11-13 12:44
- Today
- Total
Link
개발하는 고라니
[백준] 16768번 : Mooyo Mooyo 본문
반응형
[DFS]
뿌요뿌요(?)와 비슷한 방식의 게임이라고 하며, 0은 빈 칸이고, 1~9로 이루어진 각각 다른 색의 세포가 10 x N 격자에 있는데 최소 K개의 같은 색인 인접(상하좌우)한 세포가 있으면 그 덩어리는 사라지며 빈 공간으로 변경되고, 위의 애들이 중력에 의해 내려오고, 다시 터지고 내려오고를 반복해 더이상 터지지 않을 때 까지 반복하는 문제이다.
맨 아랫줄부터 DFS 탐색하며 탐색하는 정점마다 Stack에 저장하고 같은 색의 인접한 칸이 K개 이상이면 DFS를 마치고 Stack에 저장된 좌표의 값을 0(빈 공간)으로 만들어준다.
//DFS
static void DFS(int y, int x, int value){
cnt++;
visit[y][x] = true;
stack.push(new Point(y, x));
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
if(ny < 1 || nx < 1 || ny > n || nx > 10 || visit[ny][nx] || map[ny][nx] != value) continue;
DFS(ny, nx, value);
}
}
//main 일부
while(true){
visit = new boolean[101][11];
boolean flag = false;
downward();
for(int i=n; i>0; i--)
for(int j=1; j<=10; j++){
if(visit[i][j] || map[i][j] == 0) continue;
stack.clear();
cnt = 0;
DFS(i, j, map[i][j]);
if(cnt >= k) {
flag = true;
for (Point p : stack)
map[p.y][p.x] = 0;
}
}
if(!flag) break;
}
# Code </>
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 y, x;
public Point(int yy, int xx){
y=yy;
x=xx;
}
}
static Stack<Point> stack = new Stack<>();
static int n, k, cnt;
static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
static int[][] map = new int[101][11];
static boolean[][] visit;
static void downward(){
for(int i=n-1; i > 0; i--)
for(int j=1; j<=10; j++) {
//현재 정점이 0 또는 아래 정점이 !0
if (map[i][j] == 0 || map[i + 1][j] != 0) continue;
int z = i+1;
while(z <= n && map[z][j] == 0){
map[z][j] = map[z-1][j];
map[z-1][j] = 0;
z++;
}
}
}
static void DFS(int y, int x, int value){
cnt++;
visit[y][x] = true;
stack.push(new Point(y, x));
for(int a=0; a<4; a++){
int ny = y+Y[a];
int nx = x+X[a];
if(ny < 1 || nx < 1 || ny > n || nx > 10 || visit[ny][nx] || map[ny][nx] != value) continue;
DFS(ny, nx, value);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
for(int i=1; i<=n; i++){
char[] str = br.readLine().toCharArray();
for(int j=1; j<=10; j++)
map[i][j] = str[j-1] - '0';
}
while(true){
visit = new boolean[101][11];
boolean flag = false;
downward();
for(int i=n; i>0; i--)
for(int j=1; j<=10; j++){
if(visit[i][j] || map[i][j] == 0) continue;
stack.clear();
cnt = 0;
DFS(i, j, map[i][j]);
if(cnt >= k) {
flag = true;
for (Point p : stack)
map[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(map[i][j]);
sb.append('\n');
}
System.out.print(sb);
}
}
반응형
'Programming > 백준' 카테고리의 다른 글
[백준] 1034번 : 램프 (0) | 2021.05.10 |
---|---|
[백준] 9655번 : 돌 게임 (0) | 2021.05.10 |
[백준] 17244번 : 아맞다우산 (0) | 2021.05.06 |
[백준] 12886번 : 돌 그룹 (0) | 2021.05.02 |
[백준] 14950번 : 정복자 (0) | 2021.05.02 |
Comments