백준 2933 <미네랄>

조건이 많아서 처리해야 될 부분이 많은 시뮬레이션 문제였다.

문제의 단계는

1. 왼,오 순서대로 그 위치에 가장 가까운 미네랄을 사라지게 하는 것.
2. 제거한 위치를 중심으로 4 방형을 검사해 미네랄 이 있으면 그 부분이 떨어져 있는 것인지 확인!
3. 떨어져 있다면 얼마나 내려갈 수 있는지 체크!

이 순서로 진행되는 것이다.

 

이 부분에서 내가 헷갈렸던 부분이 2번에서 왜 4방향으로 해야 하는가 였다. 위 , 오른쪽, 왼쪽 이렇게 해주면 된다고 생각했는데 예외인 부분이 있었다.

그림처럼 화살표 부분을 부수게 되면 아래의 미네랄 뭉치가 동 떨어져 자유 낙하하게 되는 것이다.

 

이러한 실수를 고쳐야 문제를 빨리 풀 수 있을 텐데 ㅠㅠ

 

문제에 수행되는 총 시간 복잡도는 부수는 횟수를 수행하는 게 최대 100*총 BFS를 하기 때문에 100*100 =100*100*100=100만

내부에 좌표를 "."으로 바꿔주고 이동할 수 있는 만큼 옮겨서 "x"로 바꿔주는 횟수까지 포함하면 *3이라고 가정하면

300만 이기 때문에 풀리는 문제이다.

우선 부수는 위치를 입력할 때 거꾸로 뒤집혀있기 때문에 전체 행의 길이에서 빼서 넣어주었다.

 

또한 오른쪽 왼쪽 위치를 지정해주기 위해서 who라는 변수를 사용해서 구별을 해뒀다.

 

다음은 부수는 임무를 수행하고 떨어트리는 작업을 할 것이다.

왼쪽일 경우에는 0번째 열부터 시작하기 때문에 행의 위치를 더하면서 위치를 찾아준다.

만약 위치를 찾았다면 그지점을 "."으로 바꾸고 4방향으로 BFS를 처리해주었다.

오른쪽인 경우도 마찬가지지만 방향이 반대가 될 뿐이다.

 

다음은 BFS 부분을 살펴볼 것이다.

 

BFS의 흐름은 사용한 지점을 다시 사용하기 때문에 Queue가 아닌 ArrayList를 사용해서 값을 넣어 주었다.

 

1. BFS를 실시하면서 이어진 부분을 ArrayList에 저장
2. ArrayList에 포한된 위치를 모두 "."으로 값을 변경 
3. ArrayList에 포한된 지점을 바닥에 닿거나 다른 미네랄에 닿기 전까지 이동 횟수 구해주기
4. 이동해주기

이렇게 총 4단계로 이루어진다.

 

 

 

 

k값까지는 이동이 불가능하니 k-1만큼 이동해주기

 

이렇게 전체적 흐름이 구성된다.

 

시뮬레이션 처리할 것이 많아서 생각보다 시간이 오래 걸렸던 문제이다.

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{


	static int visit[][],R,C,N,dir[][]= {{-1,0},{0,1},{0,-1},{1,0}};//상 우 좌 하
	static String map[][];
	static int num[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(kb.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		map= new String[R][C];
		for(int i=0;i<R;i++) {
			String s=kb.readLine();
			for(int j=0;j<C;j++) {
				map[i][j]=""+s.charAt(j);
			}
		}
		N=Integer.parseInt(kb.readLine());
		num=new int[N];
		st=new StringTokenizer(kb.readLine());
		for(int i=0;i<N;i++) {
			num[i]=R-Integer.parseInt(st.nextToken());
		}
		int who=0;
		for(int i=0;i<N;i++) {
			if(who==0) {
				start(0,i);
				who=1;
			}
			else if(who==1) {
				start(1,i);
				who=0;
			}
		}
		StringBuilder sb=new StringBuilder();
		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 void start(int i, int j) {
		// TODO Auto-generated method stub
		if(i==0) {//왼
			int y=0;
			while(y<C&&map[num[j]][y].equals(".")) {
				y++;
			}
			if(y<C) {
				visit=new int[R][C];
				map[num[j]][y]=".";
				for(int k=0;k<4;k++) {
					int x1=num[j]+dir[k][0];
					int y1=y+dir[k][1];
					if(x1<0||x1>=R||y1<0||y1>=C||map[x1][y1].equals(".")||visit[x1][y1]==1) {
						continue;
					}
					find(x1,y1);
				}
			}
		}
		else {//오
			int y=C-1;
			while(y>=0&&map[num[j]][y].equals(".")) {
				y--;
			}
			if(y>=0) {
				visit=new int[R][C];
				map[num[j]][y]=".";
				for(int k=0;k<4;k++) {
					int x1=num[j]+dir[k][0];
					int y1=y+dir[k][1];
					if(x1<0||x1>=R||y1<0||y1>=C||map[x1][y1].equals(".")||visit[x1][y1]==1) {
						continue;
					}
					find(x1,y1);
				}
			}
			
		}
	}
	private static void find(int x, int y) {
		// TODO Auto-generated method stub
		ArrayList<Point> a=new ArrayList<Point>();
		int start=0;
		a.add(new Point(x,y));
		visit[x][y]=1;
		while(start<a.size()) {
			Point p=a.get(start++);
			for(int k=0;k<4;k++) {
				int x1=p.x+dir[k][0];
				int y1=p.y+dir[k][1];
				if(x1<0||x1>=R||y1<0||y1>=C||map[x1][y1].equals(".")||visit[x1][y1]==1) {
					continue;
				}
				visit[x1][y1]=1;
				a.add(new Point(x1,y1));
			}
		}
		for(int i=0;i<a.size();i++) {
			map[a.get(i).x][a.get(i).y]=".";
		}
		int k=1;
		b:while(true) {
			for(int i=0;i<a.size();i++) {
				Point p=a.get(i);
				if(p.x+k>=R||map[p.x+k][p.y].equals("x")) {
					break b;
				}
			}
			k++;
		}
		for(int i=0;i<a.size();i++) {
			map[a.get(i).x+k-1][a.get(i).y]="x";
		}
	}
}