[백준] 11559 Puyo Puyo (java)

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

11559번: Puyo Puyo

문제 이해

 

문제를 읽어보면 특별히 어렵지 않게 이해할 수 있는 문제였습니다. 중력에 의해 떨어지는 블록이 존재하고 상하좌우 같은 블록이 4개 이상 연결되어 있으면 삭제될 수 있습니다. 4개 이상 연결되어 있는 블럭의 그룹이 한 개 이상일 경우 그 블록들은 동시에 사라져야 하며 이렇게 한 번 사라지는 동작을 한 번의 연쇄라고 합니다. 또 이렇게 블록이 사라져 공중에 떠 있는 블록이 생긴다면 중력에 의해 아래 방향으로 내려와야 합니다.

 

문제에서 블럭이 주어질 때 몇 연쇄가 일어날 수 있는지 반환하시오.라는 문제입니다.

 

문제의 요점은

• 상하좌우 네 개 이상 연결되어 있는 블럭을 찾아내는 것
• 여러 블럭의 그룹이 사라져야 할 때 동시에 삭제하기
• 중력이 적용되어 떨어지는 블록의 움직임 구현하기

이렇게 세 가지를 어떻게 구현하느냐 였던 것 같습니다. 그래도 이 같이 구현하는 문제는 조금 적응이 된 저로서는 어렵지 않게 문제를 구상하였고, 크게 오랜 시간을 들이지 않아서 풀어낼 수 있었습니다. 문제에 대한 풀이는 주석을 통해서 서술하도록 하겠습니다.

 

public class Main {
	static char[][] board;
	static int[] dy = {0, 0, 1, -1};
	static int[] dx = {1, -1, 0, 0};
	static int cnt;
	static ArrayList<ArrayList<int[]>> nodes;
	static boolean[][] visited;
	
	public static void main(String[] args) throws Exception{
		board = new char[12][6];
		
		cnt = 0;
		nodes = new ArrayList<ArrayList<int[]>>();
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 12; i++) {
			board[i] = br.readLine().toCharArray();
		}
		
		//뿌요가 4개이상 연결 된 것이 없을 때 까지 반복해줍니다.
		while(true) {
			visited = new boolean[12][6];
			int nowCnt = 0; //연결된 뿌요가 4개이상 존재하는 즉 영역의 개수를 세어줍니다.
			
			//모든 좌표를 확인하여 줍니다.
			for (int i = 0; i < 12; i++) {
				for (int j = 0; j < 6; j++) {
					
					//블럭이 존재한다면 탐색을 시작합니다.
					if(board[i][j] != '.' && !visited[i][j]) {
						
						//현재 위치의 블럭이 무엇인지 담아두고
						//해당 블럭의 좌표를 담아줍니다.
						char nowC = board[i][j];  
						nodes.add(new ArrayList<int[]>());
						nodes.get(nowCnt).add(new int[] {i, j});
						
						//4방향을 탐색하기 위한 bfs를 위한 q를 생성합니다.
						//그리고 현재 위치는 미리 방문표시 해놓습니다.
						Queue<int[]> q = new LinkedList<>();
						q.add(new int[] {i, j});
						visited[i][j] = true;
						
						while(!q.isEmpty()) {
							//현재 노드를 꺼내어주고
							int[] node = q.poll();
							
							//상하좌우 중 같은 뿌요를 가진 것들을 찾아 q에 추가해줍니다.
							for (int k = 0; k < 4; k++) {
								int ny = node[0] + dy[k];
								int nx = node[1] + dx[k];
								
								//범위 안에 존재하고, 아직 방문한적이 없고, 같은 뿌요일 경우
								//방문처리 해주고, 같은 뿌요의 무리에 추가, 그리고 q에 추가해줍니다.
								if(0<=ny && ny<12 && 0<=nx && nx<6 && !visited[ny][nx] && board[ny][nx] == nowC) {
									visited[ny][nx] = true;
									nodes.get(nowCnt).add(new int[] {ny, nx});
									q.add(new int[] {ny, nx});
								}
							}
						}
						
						//현재 담겨진 뿌요가 4개 이상이라면 사라져야할 뿌요입니다.
						//4보다 작다면 해당 뿌요는 remove 해줍니다.
						if(nodes.get(nowCnt).size()>=4) {
							nowCnt++;
						} else {
							nodes.remove(nowCnt);
						}
					}
				}
			}
			
			//위의 과정을 통해서 이번 맵에 사라져야 할 뿌요 그룹이 하나라도 존재한다면
			//해당 뿌요들을 모두 '.'으로 변경해줍니다.
			if(nowCnt>0) {
				for (int i = 0; i < nodes.size(); i++) {
					ArrayList<int[]> now = nodes.get(i);
					for (int j = 0; j < now.size(); j++) {
						int[] nowNode = now.get(j);
						board[nowNode[0]][nowNode[1]] = '.';
					}
				}
				
				cnt++; //현재 위치의 블럭을 담아주고 
				nodes.clear(); //그리고 다음 탐색을 위해 nodes를 비워주고
				gravity();	   //중력을 적용시켜 줍니다.
				
			//사라질 뿌요가 하나도 없다면 반복을 바로 중단시켜버립니다.
			} else {
				break;
			}
			
		}
		
		//정답 출력!!
		System.out.println(cnt);
	}
	
	//중력이 적용하는 모습을 보여줍니다.
	static void gravity() {
		
		//스택 자료구조를 이용해 중력을 표현해 주었습니다.
		Stack<Character> st = new Stack<>();
		
		//세로로 한 줄씩 탐색하며 나오는 블럭들을 스택에 담아주었고,
		//탐색이 끝 난 뒤 해당 줄의 가장 하단부터 하나씩 꺼내어 줌으로서 중력을 표현하였습니다.
		for (int i = 0; i < 6; i++) {
			
			//블럭 찾기
			for (int j = 0; j < 12; j++) {
				if(board[j][i] != '.') {
					st.add(board[j][i]);
					board[j][i] = '.';
				}
			}
			
			//가장 아래부터 하나씩 쌓아주기
			int idx = 11;
			while(!st.isEmpty()) {
				board[idx][i] = st.pop();
				idx--;
			}
		}
	}
	
}

그래도 시뮬레이션 문제에 있어서는 쪼오오오오금 자신이 있을지도..