[백준_11559번] Puyo Puyo

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

11559번: Puyo Puyo

[문제]

뿌요뿌요의 룰은 다음과 같다.

 

• 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
• 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
• 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
• 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
• 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

 

 남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

 

[입력 조건]

 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

 입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.

 

[코드]

import java.util.*;

class Puyo_11559 {
	int x,y;
	
	public Puyo_11559(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_11559 {
	static char[][] map=new char[12][6];
	static boolean[][] visited;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {1,-1,0,0};
	static int count=0,result=0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		for(int i=0;i<12;i++) {
			String str=sc.next();
			for(int j=0;j<6;j++) {
				map[i][j]=str.charAt(j);
			}
		}
		
		while(true) {
			visited=new boolean[12][6];
			
			// 연산을 수행 했는지 안했는지 체크하는 변수
			boolean flag=false;
			
			// 같은 뿌요를 찾는 과정
			for(int i=0;i<12;i++) {
				for(int j=0;j<6;j++) {
					if(!visited[i][j]&&map[i][j]!='.') {
						count=1; // i행 j열의 뿌요를 포함하기 때문에 1로 초기화
						
						/*
						 * 같은 색의 뿌요가 4개 이상 있다면 제거하기
						 * 이때 탐색을 시작할 좌표와 색깔을 매개변수로 전달
						 */
						if(findpuyo(i,j,map[i][j])) {
							flag=true; // 연산 수행
							bfs(i,j,map[i][j]); // 뿌요 제거함수 실행
						}
					}
				}
			}
			
			if(flag)
				result++; // 연쇄 횟수 증가
			
			// 연산이 수행되지 않았다면 아래로 내릴 뿌요도 없기 때문에 while문 종료
			else
				break;
			
			// 뿌요가 터지는 연산이 수행 됐다면 아래로 내리기
			while(true) {
				boolean check=false; // 연상 수행 여부 체크
				
				check=gravity(check);
				
				// 아래로 내려갈 뿌요가 없다면 while문 종료
				if(!check)
					break;
			}
		}
		
		System.out.println(result);
	}
	
	// x행 y열을 기준으로 주변에 color와 같은 색상의 뿌요를 제거하는 함수
	public static void bfs(int x, int y, char color) {
		Queue<Puyo_11559> q=new LinkedList<>();
		q.add(new Puyo_11559(x,y));
		
		while(!q.isEmpty()) {
			Puyo_11559 puyo=q.poll();
			
			x=puyo.x;
			y=puyo.y;
			
			for(int i=0;i<4;i++) {
				int nx=x+dx[i];
				int ny=y+dy[i];
				
				// 배열의 범위를 벗어났거나 같은 색깔이 아니라면 넘어간다.
				if(nx>=12||ny>=6||nx<0||ny<0||map[nx][ny]!=color)
					continue;
				
				/*
				 * x행 y열을 기준으로 주변에 color와 같은 색생의 좌표를
				 * 4개 이상의 개수를 셀 때 true 처리가 되었기 때문에 해당 좌표에 있는 쀼요들을 떠뜨리기
				 */
				if(visited[nx][ny]&&map[nx][ny]==color) {
					map[nx][ny]='.'; // 떠뜨리기
					q.add(new Puyo_11559(nx,ny));
				}
			}
		}
	}
	
	// 주변에 color 색을 갖는 쀼요가 4개 이상 있는지 확인하는 함수
	public static boolean findpuyo(int x, int y, char color) {
		visited[x][y]=true; // 여기서 true 처리 -> bfs 함수에서 true 값인 쀼요를 제거해야 한다.
		
		// 상,하,좌,우 탐색
		for(int i=0;i<4;i++) {
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			// 배열 벗어난 경우 넘어간다.
			if(nx>=12||ny>=6||nx<0||ny<0)
				continue;
			
			// 같은 색상이 아니거나 이미 방문처리 된 곳이라면 넘어간다.
			if(map[nx][ny]!=color||visited[nx][ny])
				continue;
			
			count++; // 개수 증가
			findpuyo(nx,ny,color);
		}
		
		if(count>=4) // 주변에 같은 색인 쀼요가 4개 이상이라면 return true
			return true;
		else
			return false;
	}
	
	// 쀼요가 터지고 나서 남아있는 쀼요를 밑으로 내리는 함수
	public static boolean gravity(boolean check) {
		// 배열의 위에 있는 쀼요들을 아래로 옮겨야하기 때문에 값을 줄여나가야 한다.
		for(int i=11;i>0;i--) {
			for(int j=5;j>=0;j--) {
				// 빈 공간 위의 행에 뿌요가 있는 경우는 아래로 내려야 함
				if(map[i][j]=='.'&&map[i-1][j]!='.') {
					check=true;
					map[i][j]=map[i-1][j];
					map[i-1][j]='.';
				}
			}
		}
		
		return check;
	}
}

 

[고찰] 

 이번 문제 또한 이전 빙산 문제와 같이 구현해야 하는 조건들도 많고 로직도 복잡해 다른 사람의 코드를 참고하며 해결하였다. 문제를 크게 3가지로 나눠볼 수 있다.

 

첫 번째, 뿌요를 찾았을 때 자신을 기준으로 주변에 같은 색상의 뿌요가 4개 이상인지 찾기 (findpuyo 함수) 

두 번째, 찾은 뿌요가 4개 이상이라면 터뜨리기 (dfs 함수)

세 번째, 뿌요 밑에 빈 공간이 있다면 아래로 내리기 (gravity 함수)

 

 이때 몇 가지 주의해야 할 점도 있다. 같은 레벨인 경우 뿌요를 터뜨리는 과정이 여러번 반복되더라도 1번의 연쇄로 치기 때문에 while문을 사용하여 모든 배열을 탐색한 후에 한 번만 값을 증가시켜야 한다. 또한 뿌요는 자신을 포함한 근처에 4개 이상의 같은 색상의 뿌요를 찾는 과정에서(findpuyo 함수) 좌표들을 true 처리 해주었기 때문에 후에 dfs 함수에서 해당 뿌요들을 제거할 때 visited 배열의 값이 true인 좌표들을 찾아 제거해주어야 한다. 마지막으로 빈 공간 위에 뿌요가 있는 경우 아래로 내리는 gravity 함수에서 배열의 인덱스를 주의해야 한다. 뿌요는 행과 열의 크기가 작은 곳에서 큰 곳으로 옮겨야 하며, 행의 이동만 있기 때문에 열은 건들이면 안된다. 

 

 이번 문제 또한 복잡한 BFS 문제였다. 이후 삼성 기출문제를 풀기 위해서는 이런 난이도의 문제들을 더 많이 접해봐야 한다고 생각하기 때문에 좀 더 복잡한 문제들을 위주로 도전하려 노력중이다.