[자바] 백준 11559 - Puyo Puyo (java)

 문제 : boj11559

---

 

필요 알고리즘 개념

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

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

 

---

 

풀이

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

 

시뮬레이션으로 생각해본다면 다음의 과정을 진행하면 된다.

1. 연결된 4개이상의 뿌요들을 없앤다. 없앨 수 있는 뿌요가 있는 경우 '1'이 진행된 횟수를 따로 기록해둔다.

2. '1'에서 없어진 뿌요들의 자리를 중력의 영향을 받도록 내려준다.

3. '1'에서 없앨 수 있는 뿌요가 없을 때 까지 '1'과 '2'를 진행하고, 더이상 없다면 '1'에서 기록해둔 횟수를 출력해준다.

 

  코드로 로직 부분을 보면 간단히 아래와 같다. '1'은 puyopuyo(), '2'는 getDropMap 이다.

int cnt = 0;
while (puyopuyo(map)) {
    cnt++;
    map = getDropMap(map);
}
System.out.println(cnt);

 

- puyopuyo()는 map에서 연결된 4개이상의 뿌요들을 없앤다. 

 

- getDropMap() 에서 중력의 영향으로 아래로 모두 내려온 뿌요지도로 교체한다.

 

- 더이상 4개이상 모이지 않을때 까지 계속 해준다.

 

 

---

 

코드 : 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 = 12;
    private static int COL = 6;
    private static final int REMOVE_CNT = 4;
    private static final char BLANK = '.';

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
    
    private boolean puyopuyo(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 {
        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);
            }
        }
        int cnt = 0;
        while (puyopuyo(map)) {
            cnt++;
            map = getDropMap(map);
        }
        System.out.println(cnt);
    }
}