[백준/Java] 2933번 미네랄

1. 문제

 

이 문제는 그래프 탐색을 기반으로 한 구현문제이다.

동굴의 미네랄을 파괴하며 클러스터가 분리되면

새롭게 생성된 클러스터를 아래로 떨어뜨리는 문제이다.

 

2. 풀이

 

문제를 이해하기 위해서 해야 하는 일을 순서대로 정리해보았다.

 

<문제 접근 방법>
1. 동굴 입력 받기
2. 높이와 막대 던지는 방향 확인해서 미네랄 파괴하기
3. 파괴된 미네랄 주변 클러스터 분리 여부 확인하기
4. 분리된 클러스터를 아래로 떨어뜨리기
5. 2 ~ 4번 반복하기
6. 최종 미네랄 모양 출력하기

 

1. 동굴 입력 받기

동굴을 char[][] 배열로 입력 받는다.

'x'는 미네랄이고 '.'은  빈 공간이다.

 

2. 높이와 막대 던지는 방향 확인해서 미네랄 파괴하기

가장 아래가 1층이므로 높이 h가 주어졌을 때 r - h로 해당 층 좌표를 구할 수 있다.

던지는 방향은 왼 -> 오 -> 왼 -> 오 가 반복된다.

boolean isLeft를 만들어두고 !isLeft를 통해 계속 왼 -> 오를 번갈아 가면서 탐색을 다르게 한다.

만약 isLeft가 true라면 0부터 탐색을, false라면 c-1 부터 탐색을 하며 파괴할 미네랄을 찾아 '.'으로 바꾼다.

 

3. 파괴된 미네랄 주변 클러스터 분리 여부 확인하기 dfs()

바닥과 연결된 클러스터는 파괴되지 않으므로 모두 방문처리를 해준다.

파괴된 미네랄로부터 4방 탐색을 실행하다 아직 방문처리가 되지 않은 미네랄을 발견한다면!

방문 배열을 초기화하고 그 미네랄로부터 dfs로 연결된 모든 미네랄을 탐색한다.

만약 파괴된 미네랄로부터 4방의 모든 미네랄이 방문처리되었었다면 클러스터는 분리되지 않은 것이다.

 

4. 분리된 클러스터를 아래로 떨어뜨리기 downCluster()

분리된 클러스터의 높이를 확인하고 어디까지 떨어뜨릴 수 있는지 확인한다.

떨어뜨릴 수 있는 줄을 확인하고나서 해당 위치까지 미네랄을 떨어뜨린다.

말로는 간단하지만 인덱스 처리에 애를 먹었던 부분...

 

5. 2 ~ 4번 반복하기

위의 과정을 순서대로 실행하며 n번에 걸쳐 미네랄을 파괴하고 동굴을 갱신한다.

 

6. 최종 미네랄 모양 출력하기

출력량이 많으니 StringBuilder를 사용하여 출력해주면 끝!

 

3. 코드

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

public class Main {
	static int r, c;
	static boolean[][] visited;
	static char[][] cave;
	static int[] dr = {1, -1, 0, 0};
	static int[] dc = {0, 0, 1, -1};

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		cave = new char[r][c];
		String input;
		
		for (int i = 0; i < r; i++) {
			input = br.readLine();
			for (int j = 0; j < c; j++) {
				cave[i][j] = input.charAt(j);
			}
		}
		
		int row, col, nr, nc;
		boolean isLeft = false;

		
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int t = 0; t < n; t++) {
			row = r - Integer.parseInt(st.nextToken());
			col = -1;
			isLeft = !isLeft;
			
			//파괴될 미네랄 위치 찾기
			if (isLeft) {
				for (int j = 0; j < c; j++) {
					if (cave[row][j] == 'x') {
						col = j;
						break;
					}
				}
			} else {
				for (int j = c - 1; j >= 0; j--) {
					if (cave[row][j] == 'x') {
						col = j;
						break;
					}
				}
			}
			
			//만약 파괴되는 미네랄이 없다면 다음으로
			if (col == -1) continue;
			
			//클러스터 분리 확인
			cave[row][col] = '.';
			visited = new boolean[r][c];
			//바닥면에 닿은 미네랄을 방문 처리
			for (int j = 0; j < c - 1; j++) {
				if (!visited[r-1][j] && cave[r-1][j] == 'x') {
					visited[r-1][j] = true;
					dfs(r-1, j);
				}
			}
			//없앤 미네랄 근처 사방에 탐색 안 된 미네랄이 있는지 확인 -> 분리된 미네랄 체크
			for (int d = 0; d < 4; d++) {
				nr = row + dr[d];
				nc = col + dc[d];
				if (0 > nr || nr >= r || 0 > nc || nc >= c) continue;
				if (cave[nr][nc] == 'x' && !visited[nr][nc]) {
					visited = new boolean[r][c];
					visited[nr][nc] = true;
					dfs(nr, nc);
					downCluster();
					break;
				}
			}
		}
		
		//출력하기
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				sb.append(cave[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}
	
	static void downCluster() {
		int maxRow = 0, minRow = r-1, moveRow = -1;
		for (int i = r-1; i >= 0; i--) {
			for (int j = 0; j < c; j++) {
				if (visited[i][j]) {
					maxRow = Math.max(maxRow, i);
					minRow = Math.min(minRow, i);
				}
			}
		}
		//어디까지 떨어뜨릴 수 있는지 확인
		int idx;
		outer : for (int i = maxRow + 1; i < r; i++) {
			idx = maxRow;
			for (int k = i; k >= i - (maxRow - minRow); k--) {
				for (int j = 0; j < c; j++) {
				
					if (visited[idx][j]) {
						if ((cave[k][j] == 'x' && visited[k][j]) || cave[k][j] == '.') continue;
						break outer;
					}
				}
				idx--;
			}
			
			moveRow = i;
		}
		
		if (moveRow == minRow || maxRow == r - 1 || moveRow == -1) return;
		
		int diff = moveRow - maxRow;
		
		//떨어뜨리기
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (visited[i][j]) cave[i][j] = '.';
			} 
		}
		
		for (int i = moveRow; i >= diff; i--) {
			if (minRow == i) break;
			for (int j = 0; j < c; j++) {
				if (visited[i - diff][j]) cave[i][j] = 'x';

			}
		}
	}

	static void dfs(int r1, int c1) {
		for (int d = 0; d < 4; d++) {
			int nr = r1 + dr[d];
			int nc = c1 + dc[d];
			if (0 > nr || nr >= r || 0 > nc || nc >= c || visited[nr][nc] || cave[nr][nc] == '.') continue;
			visited[nr][nc] = true;
			dfs(nr, nc);
		}
	}
}

 

4. 느낀점

 

문제를 풀고보니 dfs 보다는 bfs를 사용했어도 좋았겠다는 생각이 들었다.

기본적인 그래프 탐색 자체는 간단하게 구현하지만

어디까지 떨어뜨릴 수 있는지 확인하여 갱신하는 과정에서

인덱스 처리의 어려움을 겪었다ㅠㅠ

 

이전에 하강 관련 문제들을 풀면서 스택을 사용하는게 좋다고 느꼈는데

이번 문제는 각 줄마다 모두 끝까지 내려가는 것이 아니라

덩어리가 내려가다 보니까 그 부분에 있어서 좀 고민을 했다.

요새 빡구현 문제를 잘 안 풀었어서 그새 실력이 떨어진 것 같아 조금 아쉽기도 하다.