[백준 JAVA] 11559번: Puyo Puyo

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static int R = 12, C = 6, ans = 0, cnt;
	public static char[][] map = new char[12][6];
	public static int[][] visited;
	public static int[][] arr;
	public static int[] dx = { -1, 0, 1, 0 };
	public static int[] dy = { 0, 1, 0, -1 };

	public static void main(String[] args) throws IOException {
		// 1. 입력값 받기
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < R; i++) {
			String str = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = str.charAt(j);
			}
		}

		arr = new int[72][2];

		// 2. . 이 아닌 원소 순회
		while (true) {
			// 2-1. b, visited 초기화
			boolean chk = false;
			visited = new int[R][C];

			// 2-2. 4개이상 이어진다면 화면에서 없애고
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if (visited[i][j] == 0 && map[i][j] != '.') {
						visited[i][j] = 1;
						arr[0][0] = i;
						arr[0][1] = j;
						cnt = 1;
						dfs(i, j, cnt, map[i][j]);
						if (cnt >= 4) {
							chk = true;
							for (int k = 0; k < cnt; k++) {
								int r = arr[k][0];
								int c = arr[k][1];
								map[r][c] = '.';
							}
						}
					}
				}
			}
			if (!chk) // 바뀐적이 없다면 break;
				break;
			
			// 빈공간을 떨어지게 만들기 값넣어주기
			for (int j = 0; j < C; j++) {
				Stack<Character> st = new Stack<>();
				for (int i = 0; i < R; i++) {
					if (map[i][j] != '.') {
						st.add(map[i][j]);
						map[i][j] = '.';
					}
				}
				int cur = R - 1;
				while (!st.isEmpty()) {
					map[cur--][j] = st.pop();
				}
			}

//			for (int i = 0; i < R; i++) {
//				for (int j = 0; j < C; j++) {
//					System.out.print(map[i][j]);
//				}
//				System.out.println();
//			}
			
			// 3. ans++후 반복
			ans++;
		}

		System.out.println(ans);

	}

	public static void dfs(int x, int y, int depth, char color) {

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= R || ny < 0 || ny >= C)
				continue;
			if (map[nx][ny] == color && visited[nx][ny] == 0) {
				visited[nx][ny] = 1;
				arr[cnt][0] = nx;
				arr[cnt][1] = ny;
				cnt++;
				dfs(nx, ny, depth + 1, color);

			}
		}
	}
}

 

풀이 사항
풀이 일자: 2024.08.27
풀이 시간: 100분 00초
채점 결과: 정답
예상 문제 유형: DFS, BFS

 

풀이 방법

맵에서 이어져있는 같은 값인 요소를 골라서 4개이상이면 맵에서 지우고 밑으로 내리게 하는 인접 탐색과 구현을 같이 물어보는 문제였다. 

 

1. 맵을 입력받고 지워야되는 원소 저장할 배열을 선언해주었다. 최대크기가 맵의 사이즈이므로 72개

 

2. 더이상 맵이 바뀌지 않을 때까지 반복하기 위해 while문 안에서 맵을 돌며 비어있지 않은 값이 들어있는 곳에 도착하면 주변에 몇개까지 이어져있는지 dfs를 돌며 확인해준다.

 

3. 4개 이상 이어져 있다면 arr 배열에 저장해둔 위치로 가서 맵에서 해당 값을 삭제해 준다.

 

4. 다 돌았는데 바뀐적이 없다면 break;

 

5. 빈공간이 생겼으면 아래로 떨어지게 만든다. 스택을 사용해서 위쪽에서부터 값이 들어있다면 삽입해주고 맵의 값을 지워준다. 끝까지 도착했다면 다시 맨밑에서 부터 꺼내준다. 만약 반대로 뒤집어서 넣어주고 싶다면 스택이 아니라 큐를 사용하면 될것같다.

 

6. ans증가시키고 2~5를 반복해준다.

 

쉽게? 풀지는 않았지만 그래도 방법을 몰라서 헤매지는 않았다. 오히려 구현부분에서 좀 애를 먹었다. 힘들었던 부분을 좀 써노려한다.

 

첫번째, 단지번호 붙이기 문제와 같이 인접한 묶음이 몇개인지 세는것과는 달리 원소가 4개 이상일때만 삭제해줘야하고 dfs내에서는 몇개인지 확정할 수 없다고 생각했다. 또한 정확한 갯수를 알지 못하기 때문에 depth에서 빠져나올때 계산할 수도 없다.즉, DFS의 기저조건을 구현할 수 없다.

 

예를든다면 

다음과 같은 블럭이 있다했을때

 

블럭의 갯수는 총 5개지만 dfs의 depth는 3까지밬에 늘어나지 않는다. 그리고 파라미터로 넣어준 값을 올리는것, int형태로 리턴값을 주는것도 어렵다고 생각했다.따라서 전역변수로 cnt를 계속 초기화해주면서 dfs에 들어갈 때마다 값을 증가시켜주었다.

 

지금 드는 생각인데 배열에 인자값을 저장하지 않고 리스트로 블럭의 좌표를 저장했다면 리스트 사이즈로 갯수를 알 수 있었을것 같다. 해당 방법으로 BFS로 구현하면 더 쉬웠을 것 같다.

 

그리고 이부분에서 값이 나왔을때 가장 오래걸린 실수가 나오게 된다.

 

if (cnt >= 4) {

chk = true;

for (int k = 0; k < cnt; k++) {

int r = arr[k][0];

int c = arr[k][1];

map[r][c] = '.';

}

}

 

cnt가 4 이상일때 맵이 바뀌었다는것을 표시해주는 chk를 true로 만들고 cnt만큼 for문을 돌면서 arr좌표에 있는 map값을 .으로 바꿔주었다. 

 

하지만 처음에 if문에 4까지 표시되었기 때문에 arr 또한 4까지 없애야하는 블럭이 들어있을 줄 알고 k의 범위를 <= cnt 까지 해주었다. 이렇게 하면 비어있을 수도 있고 값이 들어있을 수도 있는 arr값을 계속 지워주게 되서 29%에서 답이 맞지 않는다.

 

범위를 잘못지정하는 실수를 많이 하는 것 같다. 조심해서 사용하고 확실하게 사용하자.