백준 11559번 PuyoPuyo

www.acmicpc.net/problem/11559

11559번: Puyo Puyo

네 오늘 풀었던 백준 문제는 11559번 PuyoPuyo!

2015년 연세대학교 프로그래밍 경시대회에 출제되었던 문제라고 하네요.

 

뿌요뿌요라는 게임을 알기도 하고 해봤기에 문제를 푸는데 흥미도 더 생기고

재미있게 해결한 문제인거 같습니다.

 

사실 코딩 테스트 준비를 처음 시작한 작년 초에 풀어봤던 문제인데...

테스트 케이스는 되는데 반례들이 해결이 안되서

이 정도면 됐지 라는 안일한 마음으로 포기했던 문제인데요ㅠㅠ

 

이번에 다시 코딩테스트 준비를 시작하면서 다시 도전했고 풀어내게 되었네요!

다시 풀어보니 생각보다 어려운 문제가 아니었다는~~

 

처음에 헤맸던 부분은 맵이 Char로 이루어져서 입력을 받는데 애먹었네요 ㅎㅎ;

구현은 그렇게 어렵지 않았다고 생각합니다.

 

저도 그랬구 아마 테스트 케이스는 되는데 오답이라고 나온다면

연쇄가 한번 끝나고 블럭들이 바닥에 내려오게 만드는 코드가 잘못되었을 확률이 큽니다!

저도 처음엔 잘못 이해해서 그 부분이 틀렸었어요ㅎ

 

구현한 부분은 다음과 같습니다.

• BFS로 같은 색깔 블럭이 이어 붙은 부분이 4개 이상이면 제거하기!(BFS로 구현)
• 맵을 모두 탐색하여 같은 색깔 블럭이 이어 붙은 부분이 4개 이상인 부분이 한번도 없었다면 게임 종료!
• 연쇄가 끝난 뒤 블럭들을 바닥으로 끌어당기기(한 열을 탐색, 블럭들을 ArrayList에 넣어 바닥에서부터 다시 그리기!)

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	ArrayList<Point> deleteList = new ArrayList<>(); 
	Queue<Point> puyopuyoQueue = new LinkedList<>();
	char[][] map = new char[12][6];
	boolean[][] isNotVisited = new boolean[12][6];
	int[] dirX = {0,0,-1,1};
	int[] dirY = {-1,1,0,0};
	char[] color = {'R', 'G', 'Y', 'B'};
	int time = 0, deleteCount = 0;
	
	public void startPuyoPuyo() {
		int i, j;
			
		while(true) {
			deleteCount = 0;
			
			for(i=0; i<12; i++)
				Arrays.fill(isNotVisited[i], true);
			
			for(i=0; i<12; i++) {
				for(j=0; j<6; j++) {
					if(map[i][j] != '.' && isNotVisited[i][j] ) {
						bfsPuyoPuyo(i, j, map[i][j]);
					}
				}
			}
			if(deleteCount == 0)
				break;
				
			time++;
			gravity();
		}
		
		System.out.println(time);
	}
	
	public void bfsPuyoPuyo(int checkY, int checkX, char color) {
		int i, j, k, x, y;
		Point nowPoint;
		
		deleteList.add(new Point(checkX, checkY));
		puyopuyoQueue.add(new Point(checkX, checkY));
		isNotVisited[checkY][checkX] = false;
		
		
		while(!puyopuyoQueue.isEmpty()) {
			nowPoint = puyopuyoQueue.remove();
			
			for(i=0; i<4; i++) {
				x = nowPoint.x + dirX[i];
				y = nowPoint.y + dirY[i];
				if(x>=0 && x < 6 && y>= 0 && y<12 && map[y][x] == color && isNotVisited[y][x]) {
					puyopuyoQueue.add(new Point(x, y));
					deleteList.add(new Point(x, y));
					isNotVisited[y][x] = false;
				}
			}
		}
		
		if(deleteList.size() >= 4) {
			for(Point p : deleteList) {
				map[p.y][p.x] = '.';
				deleteCount++;
			}
		}
		
		deleteList.clear();
		
		/*
		for(i=0; i<12; i++) {
			for(j=0; j<6; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}System.out.println();
		*/
		return;
	}
	
	//밑으로 당기기
	public void gravity() {
		int i, j, k;
		ArrayList<Character> gravityList = new ArrayList<>();
		
		for(i=0; i<6; i++) {
			for(j=11; j>=0; j--) {
				if(map[j][i] != '.') {
					gravityList.add(map[j][i]);
					map[j][i] = '.';
				}
			}
			
			k= 11;
			
			for(char c : gravityList) {
				map[k][i] = c;
				k--;
			}
			gravityList.clear();
		}
	}
	
	public void setNum() throws IOException{
		int i, j;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		String tmp;
		for(i=0; i<12; i++) {
			tmp = bf.readLine();
			for(j=0; j<6; j++) {
				map[i][j] = tmp.charAt(j);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Main main = new Main();
		main.setNum();
		main.startPuyoPuyo();
	}

}