[백준] 2933 미네랄 - BFS + 구현 JAVA

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

2933번: 미네랄

코드설명

BFS와 구현을 활용하는 문제입니다.

 

문제로직입니다.

1. 막대기를 던진다면, 해당 막대기의 열에 해당하는 미네랄을 찾아 삭제합니다.
2. 막대기를 던진후, 해당 클러스터가 바닥에 떨어질 수 있는지 확인합니다.
   1. 해당 클러스터가 바닥에 떨어질 수 있다면, 얼음의 구조를 지키면서 바닥에 떨어질 수 있도록 처리합니다. 이떄 해당 클러스터가 한번 떨어진 이후에는 더이상 떨어지지 않습니다. 한번에 한개의 클러스터만 처리한뒤 종료시켜야 downCluster 중에 발생한 map의 변경값이 setCluster에 영향을 주지 않습니다.
   2. 해당 클러스터가 바닥에 떨어질 수 없다면, 다시 1번으로 돌아갑니다.

 

문제에서 2-1 의 조건에 해당하는 예시로는, https://www.acmicpc.net/board/view/124271 이 글을 보고 오류를 찾았습니다.

3 8
...xxxxx
...xx...
...xx...
4
1 1 1 1

answer
........
........
...xxxxx

wrong output
........
...xx...
....xxx.


answer 과정

...xxxxx
...xx...
...xx...

...xxxxx
...xx...
....x...

........
...xxxxx
...xx...

........
...xxxxx
....x...

........
........
...xxxxx

wrong output 과정
...xxxxx
...xx...
...xx...

...xxxxx
...xx...
....x...

........
...xx...
...xxxxx

........
...xx...
....xxxx

........
...xx...
....xxx.

위와 같은 예시를 통해 하나의 클러스터가 분리되었다면, 그 모양 자체로 내려와야하게 처리하기 위해 findCluster에서 downCluster가 성공했다면 바로 종료시키고 다음 얼음을 녹인뒤 다시 cluster를 내려오게 처리합니다.

 

자세한 설명은 주석에 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int R, C, N;
	public static char[][] map;
	public static int answer = 0;
	//상하좌우
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int[][] cluster;
    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());
    	
    	map = new char[R][C];
    	for(int i=0;i<R;i++) {
    		String str = br.readLine();
    		for(int j=0;j<C;j++) {
    			map[i][j] = str.charAt(j);
    		}
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		int height = Integer.parseInt(st.nextToken());
    		if(i%2 == 0) {//짝수라면, 왼쪽에서 오른쪽으로 던집니다.
    			throwStick(true, height);
    		}
    		else if(i%2 == 1) { //홀수라면, 오른쪽에서 왼쪽으로 던집니다.
    			throwStick(false,  height);
    		}
    		setCluster();
    	}
    	
    	for(int i=0;i<R;i++) {
    		for(int j=0;j<C;j++) {
    			System.out.print(map[i][j]);
    		}
    		System.out.println();
    	}
    }
    
    //leftToRightFlag : true -> 왼쪽에서 오른쪽, false : 오른쪽에서 왼쪽 
    public static void throwStick(boolean leftToRightFlag, int height) {
    	if(leftToRightFlag == true) {
    		for(int col = 0; col<C;col++) {
    			if( map[R - height][col] == 'x') {
    				map[R - height][col] = '.';
    				return ;
    			}
    		}
    	}
    	else {
    		for(int col = C-1; col>=0;col--) {
    			if( map[R - height][col] == 'x') {
    				map[R - height][col] = '.';
    				return ;
    			}
    		}    		
    	}
    }
    
    public static void setCluster() {
    	cluster = new int[R][C]; //초기값은 0
    	
    	int cluster_num = 1;
    	for(int i=0;i<R;i++) {
    		for(int j=0;j<C;j++) {
    			
    			if(map[i][j] =='x' && cluster[i][j] == 0) { //만약 미네랄이 있으면서 아직 Cluster에 속하지 않는다면
    				if( findCluster(i, j, cluster_num) == true) { //만약 한번이라도 클러스터가 떨어진것을 처리했다면 중단시킵니다.
    					return ; //종료 시켜야 downCluster로 인해 변경된 map[][]으로 인해 잘못된 연산을 진행하지 않습니다.
    				}
    				cluster_num += 1;
    			}
    			
    		}
    	}
    }
    
    public static boolean findCluster(int i, int j, int cluster_num) {
		//근처 미네랄들을 순회하면서 모두 같은 클러스터로 만들기 위해 BFS를 실행합니다.
		cluster[i][j] = cluster_num; //현재 위치는 초기 선언 (visited 처리하듯이)
		
		Queue<Node> q = new LinkedList<>();
		ArrayList<Node> arr = new ArrayList<>(); //만약 클러스터가 공중에 떠있다면 사용할 arr List
		q.add(new Node(i, j));
	
		int checkLowest = -1; //만약 checkLowest의 값이 R-1 값이면 맨 바닥에 있다는 뜻이므로 하늘에 떠있는 미네랄이 아닙니다. 그러므로 해당 미네랄 클러스터를 바닥으로 내보내지 않아도 됩니다.
		
		while(!q.isEmpty()) {
			Node temp = q.poll();
			arr.add(temp); //만약, 미네랄이 땅에 떨어진다면
			int r = temp.r;
			int c = temp.c;
			checkLowest = Math.max(checkLowest, r);
			for(int dir = 0; dir < 4; dir++) {
				int nr = r + dx[dir];
				int nc = c + dy[dir];
				if( nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
				if( cluster[nr][nc] > 0 ) continue; //이미 클러스터가 생성된 미네랄은 PASS
				if(map[nr][nc] == 'x') { //만약 미네랄일경우 새로 클러스터를 만들어줍니다. 
					cluster[nr][nc] = cluster_num;
					q.offer(new Node(nr , nc));
				}
			}
		}
		
		if(checkLowest != R-1) { //만약 클러스터가 공중에 떠있다면 바닥에 떨어져야합니다. 이전에 정리해둔 클러스터 모음에 arr
			downCluster(arr);
			return true;  //문제조건에 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 라는 조건이 있으므로 클러스가 한번 떨어진다면 종료시켜야합니다. 즉, 하나의 막대가 떨어지고 한번 검사하고, 하나의 막대가 떨어지고 한번 검사하는 과정을 거쳐야합니다. 
            //이와 같이 처리하지 않을경우 (미네랄을 내린 후 종료하지 않을경우 ), downCluster로 인해 갱신된 map[][]이 setCluster에서 잘못 계산되어 계속해서 값이 내려오게 됩니다.
            //여기서 정지조건을 처리해주어야만, map[][]의 변화값으로 인해 setCluster가 계속해서 실행되지 않습니다.
		}
		
		return false;
    }
    
    public static void downCluster(ArrayList<Node> arr) {
    	
    	int downCnt = 1; //1개씩 내려보면서 최대로 내릴 구간을 찾습니다.
    	
    	for(int i=0;i<arr.size();i++) { //이전 미네랄을 모두 지웁니다. ( 미네랄을 모두 내리기 위한 사전작업입니다. )
    		Node temp = arr.get(i);
    		map[temp.r][temp.c]= '.'; 
    	}
    	
    	while(true) {
    		boolean calculateDownCnt = false;
    		for(int i=0;i<arr.size();i++) {
    			Node temp = arr.get(i);
    			
    			if(temp.r + downCnt == R || map[temp.r + downCnt][temp.c] =='x' ) { //밑으로 한칸 내려갓을때 바닥이라면, 밑으로 한칸 내려갔을때 다른 미네랄이 이미 있다면 내려가지 못합니다.
    				downCnt -= 1; //만약 미네랄을 내렸을떄 한개라도 바닥보다 아래라면 downCnt의 크기를 감소시켜야합니다.
    				calculateDownCnt = true;
    				break;
    			}
    			
    		}
    		if(calculateDownCnt == true) //만약 미네랄의 down 범위가 계산되었다면, 종료시킵니다.
    			break;
    		
    		downCnt += 1;
    	}
    	
    	for(int i=0;i<arr.size();i++) {
    		Node temp = arr.get(i);
    		map[temp.r + downCnt][temp.c] = 'x'; 
    	}
    }
    
    
    
}

class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}