[백준] 11559 Puyo Puyo - Simulation(시뮬레이션) + BFS(너비우선탐색) JAVA

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

코드설명

Simulation(시뮬레이션) + BFS(너비우선탐색)을 활용합니다.

 

코드로직입니다.

1. simulate 메서드: 시뮬레이션하는 메서드로, 각 턴마다 그룹핑하고, 그룹마다의 개수를 셈으로써 게임을 진행합니다. 또한 4개 이상의 퍼즐이 모여있는 그룹이 있다면 삭제 작업을 진행합니다.
2. groupBFS 메서드: BFS 알고리즘을 사용하여 그룹을 형성하는 메서드입니다. 각 그룹의 개수와 해당 그룹의 인덱스를 저장하며, 이 정보를 활용하여 나중에 폭파할 때 활용합니다.
3. bombBFS 메서드: BFS 알고리즘을 사용하여 4개 이상이 모인 그룹의 퍼즐을 폭파시키고, 테트리스처럼 아래로 내려주는 작업을 수행합니다.

문제에서 폭파 후 테트리스처럼 내려주는 로직을 만들때, 각 열을 맨 아래 행에서부터 올라가며 최대한 내릴 수 있도록 내림처리합니다. 또한 내린 이후에는 내린칸은 빈칸으로 바꿔줍니다.

//모두 지웠다면, 이제 내려줘야한다. 
for(int j=0; j<6;j++) {
    for(int i=11; i>=0; i--) {
        if(map[i][j] != '.') {
            int startRow = i;
            while(startRow < 11) {
                if( map[startRow + 1][j] == '.' ) {
                    startRow += 1;
                }else {
                    break;
                }
            }

            if(startRow > i) {
                map[startRow][j] = map[i][j];
                map[i][j] = '.';
            }

        }

    }
}

 

처음에 시간초과가 발생할까봐 걱정했는데, 항상 테이블이 12x6 으로 고정되어있으므로 걱정할 필요가 없습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, K;
	public static int[] arr;
	public static char[][] map;
	public static int answer = 0;
	public static int groupIdx = 0;
	public static int[][] groupMap;
	public static int[][] groupCnt;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int maxCnt = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	map = new char[12][6];
    	for(int i=0;i<12;i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
		}
    	groupMap = new int[12][6];
    	groupCnt = new int[12][6];
    	groupIdx = 0;
    	
    	simulate();
    	System.out.println(answer - 1);
    }
    
    public static void simulate() {
    	
    	
    	//각 턴    	
    	answer = 0;
    	while(true) {
    		answer += 1;
    		
    		//그룹핑하고, 각 그룹마다의 개수를 모두 셌습니다.
    		//또한 만약 4개를 폭파시킬경우에만 지속합니다.
    		groupBFS();
    		
    		//각 그룹의 개수가 4개 이상인 그룹이 있다면, 삭제 작업을 진행합니다.
    		if( bombBFS() == false) {
    			break;
    		}
    	}
    	
    }
    public static boolean bombBFS() {
    	Queue<Node> q = new LinkedList<>();
    	boolean flag = false;
    	for(int i=0;i<12;i++) {
    		for(int j=0;j<6;j++) {
    			//만약 4보다 크거나 같다면, 
    			if(groupCnt[i][j] >= 4 && map[i][j] != '.') { 
    				int storeGroupIdx = groupMap[i][j];
    				map[i][j] = '.';
    				groupCnt[i][j] = 0;
    				q.offer(new Node(i, j, 0));
    				while(!q.isEmpty()) {
    					Node temp = q.poll();
    					
    					for(int dir = 0; dir < 4; dir++) {
    						int nr = temp.r + dx[dir];
    						int nc = temp.c + dy[dir];
    						
    						if(nr < 0 || nr >= 12 || nc < 0 || nc >= 6) continue;
    						if(groupMap[nr][nc] != storeGroupIdx) continue;
    						if(groupCnt[nr][nc] == 0) continue;
    						groupCnt[nr][nc] = 0;
    						map[nr][nc] = '.';
    						q.offer(new Node(nr, nc, temp.cnt + 1));
    						flag = true;
    					}
    					
    				}
    				
    			}
    		}
    	}
    	
    	//모두 지웠다면, 이제 내려줘야한다. 
    	for(int j=0; j<6;j++) {
    		for(int i=11; i>=0; i--) {
    			if(map[i][j] != '.') {
    				int startRow = i;
    				while(startRow < 11) {
    					if( map[startRow + 1][j] == '.' ) {
    						startRow += 1;
    					}else {
    						break;
    					}
    				}
    				
    				if(startRow > i) {
						map[startRow][j] = map[i][j];
						map[i][j] = '.';
					}
    				
    			}
    			
    		}
    	}
    	return flag;
    }
    
    public static void groupBFS() {
    	Queue<Node> storeQ = new LinkedList<>();
    	groupIdx = 1;
    	maxCnt = 0;
    	groupMap = new int[12][6];
    	groupCnt = new int[12][6];
    	for(int i=0;i<12;i++) {
    		for(int j=0;j<6;j++) {
    			
    			if(groupMap[i][j] == 0) {
    				maxCnt = 0;
    				Queue<Node> q = new LinkedList<>();
            		q.offer(new Node(i, j, 0));
            		storeQ.offer(new Node(i, j, 0));
            		groupMap[i][j] = groupIdx;
            		maxCnt += 1;
            		char puyo = map[i][j];
            		while(!q.isEmpty()) {
            			Node temp = q.poll();
            			
            			for(int dir = 0; dir<4; dir++) {
            				int nr = temp.r + dx[dir];
            				int nc = temp.c + dy[dir];
            				
            				if(nr < 0 || nr >= 12 || nc < 0 || nc >= 6) continue;
            				if(groupMap[nr][nc] != 0) continue;
            				if(map[nr][nc] != puyo) continue;
            				groupMap[nr][nc] = groupIdx;
            				maxCnt += 1;
            				q.offer(new Node(nr, nc, temp.cnt + 1));
            				storeQ.offer(new Node(nr, nc, temp.cnt + 1));
            			}
            		}
            		groupIdx += 1;
            		
            		while(!storeQ.isEmpty()) {
            			Node temp = storeQ.poll();
            			groupCnt[temp.r][temp.c] = maxCnt; 
            		}
    			}
    			
    		}
    	}

    }
    
}

class Node{
	int r;
	int c;
	int cnt;
	public Node(int r, int c, int cnt) {
		this.r = r;
		this.c = c;
		this.cnt = cnt;
	}
}