[BaekJoon] 16768 Mooyo Mooyo (Java)

🔗 문제 링크

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);
      }
    }

}