BOJ. 2933번. 미네랄,미네랄2

문제는 미네랄과 미네랄2가 동일하며, 같은소스로 시간차 거의 없이 통과된다.

    구현(시뮬레이션) + BFS 조합의 문제이다. 클러스터가 다른 클러스터 더미에 매달리는(?) 예외를 잘 해석하면 풀 수 있다. 예외케이스를 처리하는데 생각보다 시간이 엄청 오래 걸렸다.

1. 막대기를 쏘는 방향을 좌,우 번갈아가며 선택한다.
2. 방향에 맞춰 미네랄을 파괴한다
3. 파괴한 상태에서 BFS탐색으로 공중에 떠있는 클러스터와, 아닌 클러스터를 구분한다.
4. 공중에 떠있는 클러스터만을 아래로 최대한 하강시킨다.

  1,2,3번은 금방 처리했으나 4번에서 시간이 좀 걸렸다. 그냥 클러스터를 한칸씩 내려보며 안겹칠때까지 확인해보는 방법이 편하다. 각 라인마다 가능한 움직임을 계산하고, 그 최소값을 다시 계산하려다보니 복잡해졌다. 또한 예외처리를 미리 생각해두고 문제에 접근하면 훨씬 시간을 절약할 수 있는 것 같다.

www.acmicpc.net/problem/2933

2933번: 미네랄

 

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

public class Main {

	static int r,c,n;
	static char[][] map;
	static boolean[][] totalCheck;
	static int[] shot;
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	
	static class Pos{
		int y, x;
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		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 in = br.readLine();
			for(int j=0; j<c; j++) {
				map[i][j] = in.charAt(j);
			}
		}
		n = Integer.parseInt(br.readLine());
		shot = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			shot[i] = Integer.parseInt(st.nextToken());
		}
		solution();
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	
	private static void solution() {
		for(int i=0; i<n; i++) {
			int h = r - shot[i];
			int w;
			if(i%2==0) { // 왼쪽에서 쏘는 경우
				w = 0;
				while(w<c && map[h][w]!='x') w++;
			}else { // 오른쪽에서 쏘는 경우
				w = c-1;
				while(w>=0 && map[h][w]!='x') w--;
			}
			if(w>=0 && w<c) {
				map[h][w] = '.';
			}
			searchClusters();
//			print();
		}
	}

	private static void searchClusters() {
		// 클러스터들을 찾는다.
		// 공중에 떠 있는놈만을 대상으로 한다.
		totalCheck = new boolean[r][c];
		boolean[][] caseCheck = new boolean[r][c];
		for(int i=0; i<r; i++) {
			Arrays.fill(totalCheck[i], false);
		}
		
		
		for(int i=0; i<r; i++) {
			for(int j=0; j<c; j++) {
				if(map[i][j]=='x' && !totalCheck[i][j]) {
					for(int k=0; k<r; k++) {
						Arrays.fill(caseCheck[k], false);
					}
					bfs(i,j,caseCheck);
				}
			}
		}
		
		
	}
	
	private static void bfs(int i, int j, boolean[][] check) {
		boolean flag = false;
		Queue<Pos> q = new LinkedList<Pos>();
		q.add(new Pos(i,j));
		check[i][j] = true;
		if(i==r-1) flag=true;
		while(!q.isEmpty()) {
			Pos cur = q.poll();
			
			for(int d=0; d<4; d++) {
				int ny = cur.y+dy[d];
				int nx = cur.x+dx[d];
				if(checkBound(ny, nx) && !check[ny][nx] && map[ny][nx]=='x') {
					q.add(new Pos(ny,nx));
					check[ny][nx] = true;
					if(ny==r-1) flag=true;
				}
			}
		}
		if(flag) { //땅에 붙은놈이면
			for(int y=0; y<r; y++) {
				for(int x=0; x<c; x++) {
					if(check[y][x]) totalCheck[y][x]=true;
				}
			}
		}else { // 공중에 뜬놈이면
			ArrayList<Pos> list = new ArrayList<Pos>();
			for(int x=0; x<c; x++) {
				for(int y=r-1; y>=0; y--) {
					if(check[y][x]) list.add(new Pos(y,x));
				}
			}
			int down = 1;
			while(true) {
				boolean canDown = true;
				for(Pos p : list) {
					int ny = p.y+down;
					int nx = p.x;
					if(ny>r-1 || (map[ny][nx]=='x' && !check[ny][nx])) {
						canDown=false;
					}
				}
				if(!canDown) break;
				down++;
			}
			down--;
			for(Pos p : list) {
				int ny = p.y+down;
				int nx = p.x;
				map[ny][nx] = map[p.y][p.x];
				map[p.y][p.x] = '.';
			}
			
		}
		
	}
	
	private static boolean checkBound(int y, int x) {
		return (y>=0 && y<r && x>=0 && x<c) ? true : false;
	}
}