[BOJ 11559] Puyo Puyo (Java)

BOJ 11559 Puyo Puyo

문제풀이

현대카드 코딩 테스트를 보고나서 굉장히 충격에 빠졌다. 어렵지 않은 문제들이였는데 만족스러운 결과를 얻지 못했기 때문이다. 요인을 분석해보자면 구현력이 떨어지고 디버깅 과정이 깔끔하지 못하고 멍때리는 시간이 많았다. 반복 학습으로 자주 나오는 코드는 바로 작성할 수 있도록 외우는 수 밖에...

• 대부분의 함수를 바로 구현할 수 있었다. 근데 전체적인 구조를 어떻게 작성할지 너무 고민했다.
• 배열 중간의 빈공간을 아래로 당겨서 채우는 함수는 자주 등장하는데 너무 생각을 많이 했다.

이 문제는 4번 문제와 거의 동일한 문제였다.

• 터뜨리고
  • BFS로 탐색하여 같은 색상의 블럭이 4개 이상 되는 지점을 찾는다.
  • 다시 BFS로 같은 색상인 블럭을 모두 터뜨린다.
• 당긴고
  • 단순히 아래서 위로 인덱싱하다가 처음으로 빈 칸을 만나는 지점에서부터 다시 위로 인덱싱하며 처음으로 빈 칸이 아닌 부분을 만났을 때 당긴다.

구현코드

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

public class Main {
	
	static class Node {
		int r, c;
		
		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static char[][] map;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ans = 0;
		map = new char[12][6];
		
		char[] line = null;
		for(int r = 0 ; r < 12 ; ++r) {
			line = br.readLine().toCharArray();
			for(int c = 0 ; c < 6 ; ++c) { 
				map[r][c] = line[c];
			}
		}
		
		while(pang()) {
			fallDown();
			ans++;
		}
		
		System.out.println(ans);
	}
	
	private static void fallDown() {
		for(int c = 0 ; c < 6 ; ++c) {
			for(int sr = 11 ; sr >= 0 ; --sr) {
				if(map[sr][c] == '.') {
					for(int nr = sr - 1 ; nr >= 0 ; --nr) {
						if(map[nr][c] != '.') {
							map[sr][c] = map[nr][c];
							map[nr][c] = '.';
							break;
						}
					}
				}
			}
		}
	}

	private static boolean pang() {
		boolean flag = false;
		
		for(int r = 0 ; r < 12 ; ++r) {
			for(int c = 0 ; c < 6 ; ++c) {
				if(map[r][c] == '.') continue;
				
				if(check(r, c) >= 4) {
					boom(r, c, map[r][c]);
					flag = true;
				}
			}
		}
		
		return flag;
	}

	private static void boom(int sr, int sc, char color) {
		Queue<Node> q = new LinkedList<>();
		
		map[sr][sc] = '.';
		q.offer(new Node(sr, sc));
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int d = 0 ; d < 4 ; ++d) {
				int nr = now.r + dir[d][0];
				int nc = now.c + dir[d][1];
				if(nr >= 12 || nr < 0 || nc >= 6 || nc < 0) continue;
				
				if(map[nr][nc] == color) {
					map[nr][nc] = '.';
					q.offer(new Node(nr, nc));
				}
			}
		}
	}

	private static int check(int sr, int sc) {
		int cnt = 1;
		Queue<Node> q = new LinkedList<>();
		boolean[][] visited = new boolean[12][6];
		
		q.offer(new Node(sr, sc));
		visited[sr][sc] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int d = 0 ; d < 4 ; ++d) {
				int nr = now.r + dir[d][0];
				int nc = now.c + dir[d][1];
				if(nr >= 12 || nr < 0 || nc >= 6 || nc < 0 || visited[nr][nc]) continue;
				
				if(map[nr][nc] == map[sr][sc]) {
					cnt++;
					q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
				}
			}
		}
		
		return cnt;
	}