[BOJ 2933] 미네랄 (Java)

BOJ 2933 미네랄

문제풀이

알고리즘을 처음 시작했을 때 접하고 기겁했던 문제인데 다시 호기롭게 도전했으나 처음 생각한 알고리즘에 문제가 있었다.

• 처음 생각한 풀이
  1. 날아가서 부딪히는 첫 번째 미네랄 제거 후, 그 미네랄의 사방에 존재하는 미네랄을 리스트에 저장한다.

  2. 리스트에서 하나씩 꺼내어 BFS를 수행하여 해당 클러스터가 바닥에 닿아있는지 아닌지를 판별하며 닿아있지 않다면 해당 클러스터의 미네랄을 전부 리스트에 저장한다.
  3. 공중에 떠있는 클러스터를 내릴 수 있는 만큼 내린다.

  구현까지 신나게 했으나... 바로 틀렸습니다. 가 떠버렸고 테스트케이스를 열심히 만들고 검색해서 넣어봤으나 모두 통과되었다. 한참을 고민한 결과 아마도 막대를 처음 맞는 미네랄 주변에서 시작하여 공중에 떠 있는 클러스터를 찾는 과정에서 어떤 경우를 포함하지 못하는듯 했다.

• 개선한 풀이
  1. 막대를 던져 첫 번쨰로 부딪히는 미네랄을 제거한다.

  2. 바닥에 닿아있는 미네랄을 모두 큐에 넣고 BFS 탐색으로 방문체크한다.
  3. 방문체크되지 않은 미네랄을 모두 내릴 수 있는 만큼 내린다.

  이렇게 구현하면 맵 전체를 훑어보게되니 놓칠래야 놓칠수 없지 않겠는가? 효율적인 것을 먼저 생각하기 보다 항상 모든 경우를 포함할 수 있는 안전한 방법을 생각하자.

구현코드

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

public class Main {
	static class Node {
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static ArrayList<Node> cluster; 
	static char[][] map;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static int R, C, N;
	static int[] stick;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = stoi(st.nextToken());
		C = stoi(st.nextToken());
		
		// 맵 입력받기  
		map = new char[R][C];
		for(int i = 0 ; i < R ; ++i) {
			char[] line = br.readLine().toCharArray();
			for(int j = 0 ; j < C ; ++j) {
				map[i][j] = line[j];
			}
		}
		
		// stick 던지는 위치 입력받기 
		N = stoi(br.readLine());
		stick = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; ++i) {
			stick[i] = stoi(st.nextToken());
		}
		
		// 막대 던지기 
		for(int i = 0 ; i < N ; ++i) {
			// 던지는 높이 
			int r = R - stick[i];
			// 왼쪽에서 던질 때 
			if(i % 2 == 0) {
				for(int c = 0 ; c < C ; ++c) {
					if(map[r][c] == 'x') {
						map[r][c] = '.';
						break;
					}
				}
			// 오른쪽에서 던질 때 
			} else {
				for(int c = C - 1 ; c >= 0 ; --c) {
					if(map[r][c] == 'x') {
						map[r][c] = '.';
						break;
					}
				}
			}
			
			findCluster();
			if(cluster.size() != 0) dropMineral();
			cluster.clear();
		}
		print();
	}
	
	private static void findCluster() {
		cluster = new ArrayList<>();
		Queue<Node> q = new LinkedList<>();
		boolean[][] visited = new boolean[R][C];
		
		// 바닥에 붙어있는 미네랄을 모두 큐에 넣고 방문체크한다. 
		for(int c = 0 ; c < C ; ++c) {
			if(map[R - 1][c] == 'x') {
				q.offer(new Node(R - 1, c));
				visited[R - 1][c] = true;
			}
		}
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			for(int d = 0 ; d < 4 ; ++d) {
				int nr = cur.r + dir[d][0];
				int nc = cur.c + dir[d][1];
				if(nr >= R || nr < 0 || nc >= C || nc < 0 ||
				   visited[nr][nc] || map[nr][nc] == '.') continue;
				
				visited[nr][nc] = true;
				q.offer(new Node(nr, nc));
			}
		}
		
      	// 방문체크되지 않은 공중에 떠 있는 클러스터를 리스트에 담는다.
		for(int i = 0 ; i < R ; ++i) {
			for(int j = 0 ; j < C ; ++j) {
				if(map[i][j] == 'x' && !visited[i][j]) {
					cluster.add(new Node(i, j));
				}
			}
		}
	}

	private static void dropMineral() {
		int cnt = 0;
		
		// 현재 떨어질 클러스터를 모두 지운다. 
		for(Node n : cluster) {
			map[n.r][n.c] = '.';
		}
		
		// 현재 떨어질 클러스터가 몇칸이나 내려올 수 있는지 체크한다. 
		OUTER: for(int i = 1 ; i < R ; ++i) {
			for(Node n : cluster) {
				if(n.r + i >= R || map[n.r + i][n.c] == 'x') {
					break OUTER;
				}
			}
			cnt = i;
		}
		
		// 계산된 칸 만큼 이동시킨 클러스터를 새로 그린다. 
		for(Node n : cluster) {
			map[n.r + cnt][n.c] = 'x';
		}
	}

	private static void print() {
		for(int i = 0 ; i < R ; ++i) {
			for(int j = 0 ; j < C ; ++j) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}