[자바] 백준 16768 - Mooyo Mooyo (java)

 문제 : boj16768

---

 

필요 알고리즘 개념

• BFS (너비 우선 탐색) 등의 그래프탐색, 시뮬레이션
  
  • 연결된 뿌요들을 파악하기 위해 BFS, DFS와 같은 그래프 탐색이 필요하다. 그 외에는 그냥 제시된대로 시뮬레이션을 돌려주면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  그래프 탐색을 모른다면 BFS 글을 봐보자.

 

백준 11559 - Puyo Puyo의 아주 약간 상위호환이다. 개념은 완전히 동일하다.그러니 이 문제를 잘 모르겠다면, 11559 먼저 풀어보자!

 

풀이는 11559번 풀이로 대신한다. 만약 11559 풀면서 상수로 값들을 관리했다면, 매우 쉽게 이 문제도 통과할 수 있다. 내 경우에도 11559 코드에서 변경한건 11559에서 상수로 설정해둔걸 N과 K로 대체만 해줬다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int[] DR = {1, -1, 0, 0};
    private static final int[] DC = {0, 0, 1, -1};
    private static int ROW;
    private static int COL = 10;
    private static int REMOVE_CNT;
    private static final char BLANK = '0';

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
    
    private boolean muyomuyo(char[][] map) {
        boolean result = false;
        boolean[][] v = new boolean[ROW][COL];
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                if (map[i][j] == BLANK || v[i][j]) continue;

                int cnt = 1;
                List<int[]> path = new ArrayList<>();
                Queue<int[]> q = new ArrayDeque<>();
                v[i][j] = true;
                q.add(new int[]{i, j});
                path.add(q.peek());
                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    for (int d = 0; d < 4; d++) {
                        int nr = cur[0]+DR[d];
                        int nc = cur[1]+DC[d];
                        if (nr<0||nr>=ROW||nc<0||nc>=COL||v[nr][nc]||map[nr][nc]!=map[i][j]) continue;
                        v[nr][nc] = true;
                        cnt++;
                        int[] next = new int[]{nr, nc};
                        q.add(next);
                        path.add(next);
                    }
                }
                if (cnt<REMOVE_CNT) continue;
                
                for (int[] cur : path) {
                    map[cur[0]][cur[1]] = BLANK;
                    result = true;
                }
            }
        }
        
        return result;
    }
    
    public char[][] getDropMap(char[][] map) {
        char[][] newMap = new char[ROW][COL];
        for (char[] row : newMap) Arrays.fill(row, BLANK);
        for (int j = 0; j < COL; j++) {
            List<Character> col = new ArrayList<>();
            for (int i = ROW-1; i >= 0; i--) {
                if (map[i][j] == BLANK) continue;
                col.add(map[i][j]);
            }
            for (int i = 0; i < col.size(); i++) {
                newMap[ROW-1-i][j] = col.get(i);
            }
        }
        return newMap;
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        ROW = Integer.parseInt(st.nextToken());
        REMOVE_CNT = Integer.parseInt(st.nextToken());

        char[][] map = new char[ROW][COL];
        for (int i = 0; i < ROW; i++) {
            String row = br.readLine();
            for (int j = 0; j < COL; j++) {
                map[i][j] = row.charAt(j);
            }
        }
        while (muyomuyo(map)) {
            map = getDropMap(map);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                sb.append(map[i][j]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}