Baekjoon 2933 미네랄 JAVA

2933번: 미네랄

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 계속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

 

조건

[입력]

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

 

[출력]

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

 

풀이

해당 문제는 문제를 이해하는 부분이 가장 오래 걸렸고 다른 사람들의 설명을 보면서 문제를 이해할 수 있었다.

문제에 대한 설명은 아래와 같다.

한 턴마다 왼쪽 오른쪽 순으로 미네랄을 파괴한다. (단 미네랄을 한 개 파괴하면 거기서 해당 턴은 끝난다)

미네랄을 파괴하고 난 뒤 공중에 떠있는 클러스터가 있다면 모양을 유지한 체 아래로 내린다.

높이는 아래서부터 1로 시작한다.

즉 매턴마다 미네랄을 무스고 공중에 뜨는 클러스터가 있는지 체크해서 있다면 모양을 유지한 체 아래로 이동시키고 모든 턴이 종료하면 map를 출력하면 해결 가능한 문제다.

 

위의 문제 설명만 잘 체크하고 시키는 대로 구현하면 해결 가능한 문제며 아래와 같은 방식으로 구현하였다.

1. 입력 처리를 한다.

2. 턴 수만큼 반복하면서 높이를 입력받고 미네랄을 제거한다.

    1. 턴이 홀수인지 짝수인지 체크하여 왼쪽 시작 오른쪽 시작을 체크한다.

    2. 문제는 아래서부터 높이가 1,2,3이지만 배열은 위에서부터 1,2,3 이므로 높이에 대해 계산을 해서 변환해준다.

    3. 해당 높이에 미네랄 하나를 제거한다.

3. 공중에 떠있는 클러스터가 있는지 체크한다.

    1. dfs를 이용해 모든 map를 체크한다. (클러스터에 미네랄 중 하나라도 젤 아래 있다면 해당 클러스터는 떠있지 않는 경우)

    2. 공중에 떠있는 클러스터들에 대한 좌표를 리스트에 담아준다.

4. 공중에 떠있는 클러스터를 이동시킨다.

    1. map에서 클러스터 값을 초기화해준다.

    2. 이동시킬 수 있는 횟수를 체크한다. (미네랄 별로 바닥이나 다를 미네랄을 만날 때까지 아래로 이동시키며 최솟값을 갱신)

    3. 모든 클러스터 이동이 끝나면 이동 횟수만큼 클러스터를 이동시킨다.

5. 최종 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int R, C,dy[]= {-1,1,0,0} ,dx[]= {0,0,-1,1};
	static char[][] map;
	static boolean visit[][], fly_Check;
	static List<Node> list = new LinkedList<>();
	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++) {
			map[i] = br.readLine().toCharArray();
		}
		
		int T = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for (int t = 0; t < T; t++) {
			int f = Integer.parseInt(st.nextToken());
			if(t%2 == 0) {// 왼쪽에서 시작 
				bomb(f,true);
			}else {// 오른쪽에서 시작 
				bomb(f,false);
			}
			// 여기서 미네랄 떠있는거체크
			visit = new boolean[R][C];
			roop:
			for (int i = 0; i < R; i++) {
				for (int j = 0; j < C; j++) {
					if(map[i][j] =='x' && !visit[i][j]) {
						check(i,j);
						if(fly_Check) { // 공중에 떠있지 않는 클러스터 이므로 리스트 초기화시킴 
							list.clear();							
							fly_Check = false;
						}
						else { // 공중에 떠있는 경우 이제 몇번 이동가능하지 체크하고 이동 + 반복문 종료 
							move();
							break roop;
						}
					}
				}
			}
		}
		print(); // 최종 출력 
	}

	private static void move() {
		int ans = Integer.MAX_VALUE;
		for (Node n : list)  { // map 에서 클러스터 값 초기화 해줌 
			map[n.y][n.x] = '.'; 
		}
		for (Node n : list) { // 클러스터를 하나씩 빼서 최대경우만큼 이동시켜보면서 값을 이동할수있는 값을 경신한다. 
			for (int i = 1; i < R; i++) {
				if(n.y+i >= R || map[n.y+i][n.x] == 'x') {
					ans = Math.min(ans, i-1); // 더이상 이동 못하는 경우에서 -1뺀 값이랑 기존값중 최소값으로 경신 
					break;
				}
			}
		}
		for (Node n : list)  { // 이동한거 map 에 경신 
			map[n.y+ans][n.x] = 'x'; 
		}
		list.clear(); // 리스트는 초기화해야지 다음 경우에 클러스터 입력 가능 
	}

	private static void check(int y, int x) { //dfs 를 이용하여 떠있는 클러스터를 체크한다.
		visit[y][x] = true;
		if(y == R-1) // 만약 미네랄이 하나라도 바닥에 닿았다면 공중에 떠있지 않은 클러스터 
			fly_Check = true;
		list.add(new Node(y,x));
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || nx < 0 || ny >= R || nx >= C || visit[ny][nx] || map[ny][nx] == '.')
				continue;
			check(ny,nx);
		}
	}

	private static void bomb(int f, boolean b) {
		f = (R-1) - (f-1); // 문제는 아래에서부터 1 2 3 이지만 배열은 위에서부터 1 2 3 이라서 계산해주
		if(b) { // 왼쪽 오른쪽에 따라 미네랄을 하나 제거하기 
			for (int i = 0; i < C; i++) {
				if(map[f][i] == 'x') {
					map[f][i] = '.';
					return;
				}
			}
		}
		else {
			for (int i = C-1; i >= 0; i--) {
				if(map[f][i] == 'x') {
					map[f][i] = '.';
					return;
				}
			}
		}
	}
	
	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();
		}
	}
	
	static class Node{
		int y,x;
		Node(int y, int x){
			this.y = y;
			this.x = x;
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드