[백준] 2933미네랄

1. 문제

 

2. 접근방법

일단 문제부터가 조금 이해 안됐었는데

왼쪽 오른쪽 번갈아가며 막대기를 던져서 날라가다 부딪힌 미네랄은 모두 파괴된다 해서

클러스터가 통채로 부서지나? 생각했는데

예제를 보며 확인하니

최초로 맞는 미네랄 딱 하나 만 부서지는 것이다.

 

이 문제는 bfs나 dfs를 쓰면서 시뮬레이션 구현하는 문제이다.

 

개념 자체는 어렵지 않지만 구현할 부분이 많다.

 

1.막대기를 좌우로 번갈아가며 높이에 맞춰 던져보고 최초로 맞는 미네랄은 없애고 //안맞으면 아무것도 안하고

2.없어진 미네랄 상하좌우에 있는 미네랄부터 bfs나 dfs를 돌며 그 클러스터가 바닥에 닿는지 검사하고

3. 하늘에 떠있는 클러스터가 발견 되면 그 클러스터를 통채로 떨구는데

4. 클러스터 안의 미네랄 중 하나라도 바닥을 만나거나 다른 클러스터를 만나면 그만 떨구기

 

 

나는 검사하는 작업은 bfs를 이용하고 bfs를 돌면서 bfs에 들어가는 모든 미네랄을 우선순위 큐에도 넣어뒀다. 

//바닥과 가까운 순으로의 우선순위 큐

그러면 만약 검사를 했는데 하늘에 떠있는 클러스터라면

우선순위큐에서 그냥 하나씩 빼서 떨구면 되기 때문에 쉽게 구현 가능하다.

 

 

3. 풀이

1. 미네랄 위치들을 저장할 point 클래스 생성하고 comparable implements해오기

2. 맵 받고 던질거 위치들 받고 왼쪽 오른쪽 번갈아 가면서 미네랄 부수기

3. 부서진 위치의 상하좌우 중 방문하지 않았고 미네랄이 있는 곳이면 bfs쭉 돌려보고 바닥을 만나면 flag true하고 마져 다 돌리기 //돌리면서 만나는 미네랄 우선순위 큐에 다 넣어두기

4. flag가 false인 클러스터가 나오면

5. 맵 복사해서 우선순위 큐에서 하나씩 빼서 한칸씩 떨구고 떨어진 위치 다른 pq에 우선 저장

6. 큐 다 빠질때까지 문제 없이 돌리면 클러스터 한칸 내려온 것이니 복사한맵이랑 pq를 원본으로바꾸고 다시 5번으로

7. 내려오다 바닥이나 다른 미네랄을 만나면 복사본 폐기하고 원본으로 다시 2번으로

8. 다 던지고 나서의 맵 상태 출력

4. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class P2933미네랄 {
	static char map[][];
	static int R, C;
    static int dr[] = {0, -1, 0, 1};
    static int dc[] = {-1, 0, 1, 0};
	static boolean[][] visit;
	static Queue<Point> que = new LinkedList<Point>(); // 검사용
	static PriorityQueue<Point> pQue = new PriorityQueue<Point>(); // 떨구기용

	static class Point implements Comparable<Point> {
		int row, col;

		public Point(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}

		@Override
		public int compareTo(Point o) {
			return o.row - this.row; // 아랫줄 부터 ( row가 큰거부터)
		}
	}

	public static void main(String[] args) throws Exception {
		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 oneLine = br.readLine();
			for (int j = 0; j < C; j++) {
				map[i][j] = oneLine.charAt(j);
			}
		}

		int N = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		int height[] = new int[N];
		for (int i = 0; i < N; i++)
			height[i] = Integer.parseInt(st.nextToken());

		// 부순다.
		// 부순위치 상하좌우에 미네랄있으면 거기부터 bfs시작 visit처리 해주면서
		// 상 문제 없으면 좌 문제 없으면 우 다 검사하고 검사한것 중에 바닥 없으면 떨어뜨리게 클러스터 묶기
		// 클론한 맵에 맨밑줄부터 한칸씩 떨구기 우선순위큐로 한칸씩 떨궈
		// 내려갈라는데 바닥이나 다른 미네랄이면 종료
		boolean L = true;
		for (int i = 0; i < N; i++) { // 모든 던지기에 대해
			
			Point hitPoint = hit(height[i], L); // 일단 때려보고
			if (hitPoint == null) { // 안맞았으면 아무일도 안일어나기
				L = !L;
				continue;
			}

			visit = new boolean[R][C];

			for (int j = 0; j < 4; j++) {
				int row = hitPoint.row + dr[j]; // 맞은 위치 4방에 대해
				int col = hitPoint.col + dc[j];
				if (row < 0 || col < 0 || row >= R || col >= C)// 맵넘기지 말고
					continue;
				if (map[row][col] != 'x') // x가 아닌곳은 필요없고
					continue;
				if (visit[row][col]) // 이미 방문되어졌으면 필요없고
					continue;
				if (check(new Point(row, col)))// 바닥에 닿는지 쭉 검사해보자 연결된 클러스터는 다 visit되었겠지
					continue; // 바닥에 잘 닿으면 떨굴일 없으니 넘기고

				// 위를 다 지나왔으면 떨굴일이 생긴것
				while (true) { // 끝에 다다를때까지 떨궈
					if (!drop())
						break;
				}
				// 떨굴일 한번뿐이랬으니
				break;

			}
			L = !L; // 반대편 얘가 던지기
		}
		// 던지기 다 끝났으면 출력
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}

	}

	static Point hit(int height, boolean L) {
		int row = R - height;
		if (L) {
			for (int i = 0; i < C; i++) {
				if (map[row][i] == 'x') {
					map[row][i] = '.';
					return new Point(row, i);
				}
			}
		}

		else
			for (int i = C - 1; i >= 0; i--)
				if (map[row][i] == 'x') {
					map[row][i] = '.';
					return new Point(row, i);
				}
		return null;
	}

	static boolean check(Point np) {
		boolean flag = false;
		que.offer(np);
		pQue.offer(np); // 나중에 떨굴일 생기면 쓰게 미리 넣어두기
		visit[np.row][np.col] = true;
		while (!que.isEmpty()) {
			Point now = que.poll();
			if (now.row == R - 1) {// 바닥에 닿네?
				flag = true;
			}
			for (int i = 0; i < 4; i++) {
				int row = now.row + dr[i];
				int col = now.col + dc[i];

				if (row < 0 || col < 0 || row >= R || col >= C)
					continue;
				if (visit[row][col])
					continue;
				if (map[row][col] != 'x')
					continue;

				visit[row][col] = true;
				que.offer(new Point(row, col));
				pQue.offer(new Point(row, col));
			}

		}
		if (flag) {// 바닥에 닿았으니
			pQue.clear(); // 떨어뜨릴거 없어 필요없어
			return true;
		}
		return false; // 다 돌았는데 바닥에 안닿았으니 떨궈야지

	}

	static boolean drop() {
		PriorityQueue<Point> npQue = new PriorityQueue<Point>(); // 한칸씩 떨구고 다음 떨굴 상태 저장하자
		char [][] nMap = new char[R][C];
		for(int i = 0 ; i < R ; i++) {
			for(int j = 0 ; j < C ; j++) { //2차원 배열 깊은 복사
				nMap[i][j] = map[i][j];
			}
		}
		while (!pQue.isEmpty()) { // 다 떨굴때까지
			Point now = pQue.poll(); // 밑에 줄꺼 부터 나올거에여
			int row = now.row;
			int col = now.col;
			if (row + 1 >= R) { // 바닥이다? 끝
				pQue.clear();
				return false;
			}
			if (nMap[row + 1][col] == 'x') { // 떨굴라는데 미네랄이 있다? 끝
				pQue.clear();
				return false;
			}
			nMap[row][col] = '.'; // 원래 자리는 비워주고
			nMap[row + 1][col] = 'x'; // 아래 자리는 채워주고
			npQue.offer(new Point(row + 1, col)); // 또 떨구기 위해
		}

		// 다 잘 떨궈졌으면 원본들 변화
		pQue = npQue;
		for(int i = 0 ; i < R ; i++) {
			for(int j = 0 ; j < C ; j++) { //2차원 배열 깊은 복사
				map[i][j] = nMap[i][j];
			}
		}

		return true;
	}
}

5. 마치며

사실 구현이 어려운 문제라 그렇지 딱히 설명할 거리가 없다.

하나 하나 차근차근 해가다 보면 이상한데서 문제가 생겨서 아오 ㅁㄴㅇㄹ

 

나는 떨구다가 바닥이나 미네랄 만나면 pQue를 비워줬어야하는데 그 작업을 안했다가

몇 시간을 삽질 했는지 모르겠다;;

 

뭔가 맞은것 같은데 안돼도 문제는 문제가 없고 우리의 코드가 문제니 다시 천천히 잘 봐보도록 하자