[BOJ] 11559. Puyo Puyo

이 문제는 BFS를 계속 반복하면서 문제에 주어진 조건대로 구현하는 시뮬레이션 문제이다.

문제를 다소 어렵게 생각했었지만, 꼼꼼히 읽어보니 있는 그대로 구현하면 되는 문제였다. 4개이상 똑같은 알파벳이 연결된 것이 있나 BFS를 이용하여 찾고, 폭파시킨다음 맵을 아래로 내리면서 계속 반복하는 문제이다. 맵을 끌어 내리는 함수는 mapDown() 이라는 함수를 이용하였는데, 맨 아래 행부터 시작해 '.'을 찾으면 위의 있는 문자와 바꾸어 주는 형식으로 구현하였다.

package selfStudy.chap07;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_11559_PuyoPuyo {
    
    static int[] di= {-1,0,1,0};
    static int[] dj= {0,1,0,-1};
    
    static char[][] map;
    static boolean[][] visit;
    
    static boolean find;
    static int count;
    static int answer;
    
    
    static List<Pos> list = new ArrayList<>();
    static Queue<Pos> queue = new LinkedList<>();
    
    static class Pos{
        int i,j;char ch;
        public Pos(int i,int j,char c) {
            this.i=i;this.j=j;ch=c;
        }
        
    }
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        map=new char[12][6];
        
        for(int i=0;i<12;i++) {
            String str= br.readLine();
            for(int j=0;j<6;j++) {
                map[i][j]=str.charAt(j);
            }
        }
        
        list=new ArrayList<>();
        queue =new LinkedList<>();
        answer=0;
        
        while(true) {
            
            visit=new boolean[12][6];
            find=false;
            bfs();
            
            if(find==true) {
                //맵다운
                mapDown();
                answer++;    //최종결과 추가
            }else
                break;
        }
    
        System.out.println(answer);
    }
    
    static void bfs() {
        for(int i=0;i<12;i++) {
            for(int j=0;j<6;j++) {
                if(map[i][j]!='.' && visit[i][j]==false) {
                    queue.offer(new Pos(i, j, map[i][j]));
                    list.add(new Pos(i, j, map[i][j]));
                    visit[i][j]=true;
                    count=1;
                    while(!queue.isEmpty()) {
                        Pos cur = queue.poll();
                        for(int dir=0;dir<4;dir++) {
                            int nextI=cur.i+di[dir];
                            int nextJ=cur.j+dj[dir];
                            
                            if(nextI<0 || nextI>=12 || nextJ<0 ||nextJ>=6)
                                continue;
                            
                            if(map[nextI][nextJ]==cur.ch && visit[nextI][nextJ]==false) {
                                visit[nextI][nextJ]=true;
                                queue.offer(new Pos(nextI, nextJ, cur.ch));
                                list.add(new Pos(nextI, nextJ, map[i][j]));
                                count+=1;
                            }
                        }
                    }
//                    System.out.println(i+","+j+"에서 " +count+"카운팅");
                    if(count>=4) {    //4개가 연속한다면
                        //list에서 꺼내서 맵변형
                        for(Pos temp :list) {
                            map[temp.i][temp.j]='.';
                        }
                        find=true;
                    }else {        //4개가 연속이지 않는다면
                        list.clear();    //리스트 비우기
                    }
                }
            }
        }
    }
    
    static void mapDown() {
        for(int col=0;col<6;col++) {
            for(int row=11;row>=0;row--) {
                if(map[row][col]=='.') {
                    for(int up=row-1;up>=0;up--) {
                        if(map[up][col]!='.') {
                            map[row][col]=map[up][col];
                            map[up][col]='.';
                            break;
                        }
                    }
                }
            }
        }
        
    }
}