[Algorithm] 백준 11559 Puyopuyo

맞은 풀이

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static char[][] map = new char[12][6];
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        // 1:00
        // 터질 수 있는게 여러개 - 동시에 터지고 한번의 연쇄로 통합됨
        int answer = 0;
        for(int i = 0; i < 12; i++){
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            for(int j = 0; j < 6; j++) {
                map[i][j] = s.charAt(j);
            }
        }

        while(true) {
            List<List<Point>> lst = new ArrayList<>();
            int[][] visit = new int[12][6];

            // 탐색을 한다 - 조건 만족하면 List에 푸시
            for(int i = 0; i < 12; i++) {
                for(int j = 0; j < 6; j++) {
                    if(map[i][j] == '#' || map[i][j] == '.') continue;

                    List<Point> temp = new ArrayList<>();

                    Queue<Point> q = new LinkedList<>();
                    q.offer(new Point(i, j));
                    temp.add(new Point(i, j));
                    visit[i][j] = 1;
                    // bfs
                    while(!q.isEmpty()) {
                        Point poll = q.poll();

                        for(int d = 0; d < 4; d++) {
                            int nr = poll.r + dr[d];
                            int nc = poll.c + dc[d];

                            if (!OOB(nr, nc) && visit[nr][nc] == 0 && map[nr][nc] == map[i][j] ) {
                                visit[nr][nc] = 1;
                                q.offer(new Point(nr, nc));
                                temp.add(new Point(nr, nc));
                            }
                        }
                    }

                    if(temp.size() >= 4) {
                        lst.add(temp);
                    }
                }
            }

            // 없으면 stop
            if(lst.size() == 0) break;

            // 표시
            for(List<Point> l: lst) {
                for(Point p: l) {
                    map[p.r][p.c] = '#';
                }
            }
            // down
            for(int j = 0; j < 6; j++) {
                for(int i = 0; i < 12; i++) {
                    if(map[i][j] == '#') {
                        int temp = i;
                        while(temp-1 >= 0 && map[temp][j] != '.') {
                            map[temp][j] = map[temp-1][j];
                            temp--;
                        }
                        map[temp][j] = '.';
                    }
                }
            }
//            print(map);
            answer++;
        }
        bw.write(answer+"");
        bw.flush();
    }

    public static void print(char[][] map) {
        for(int i = 0; i < map.length; i++) {
            for(int j = 0; j < map[0].length; j++) {
                System.out.print(String.format("%2s", map[i][j]));
            }
            System.out.println();
        }
        System.out.println();
    }
    public static boolean OOB(int r, int c) {
        return r < 0 || r >= 12 || c < 0 || c >= 6;
    }

    public static class Point {
        int r; int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

}

틀렸던 풀이

• 내려줄 때 내려서 빈 공간에 비었다는 표시를 안하고 넘어가서 틀림
• 끝점에 대한 고려 안해서 틀림

public class Main {

    public static void main(String[] args) throws IOException {
            ...
            
            // down
            for(int j = 0; j < 6; j++) {
                for(int i = 0; i < 12; i++) {
                    if(map[i][j] == '#') {
                        int temp = i;
                        while(temp-1 >= 0 && map[temp][j] != '.') {
                            map[temp][j] = map[temp-1][j];
                            temp--;
                        }
                    }
                }
            }

    }

}