[알고리즘] Java / 백준 / 유성 / 10703

[알고리즘] Java / 백준 / 유성 / 10703

문제

문제 링크

작고 특이한 모양의 유성 사진이 인터넷에 올라왔다. 사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다. 유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 이를 복원해야 한다.

유성 사진을 문자의 배열로 단순화시켜 표기할 것이다. 문자 'X'는 유성의 일부를, 문자 '#'는 땅의 일부를, 그리고 나머지(공기)는 문자 '.'로 이루어져 있다.

모든 유성 조각들은 연결되어 있다. 즉, 두 부분 유성이 존재한다면, 한 쪽에서 유성 조각을 통해 상하좌우로 이동해서 다른 부분 유성에 도달할 수 있다. 땅 또한 같은 방식으로 연결되어 있다.

주어진 사진에서 유성은 땅보다 위에 있다. 정확히 말하자면, 적어도 한 줄 이상의 공기('.')가 존재하며, 유성은 그 보다 위에, 땅은 그 보다 아래쪽에 있다. 또한, 사진의 맨 밑 줄은 모두 땅이다.

유성은 수직으로 낙하한다. 유성이 땅에 떨어졌을 때, 유성과 땅은 원형을 유지한다고 한다. 유성이 떨어진 후의 사진을 복구하여라.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_10703 {

	static class Star{
		int r;
		int c;
		
		Star(int r,int c){
			this.r=r;
			this.c=c;
		}
	}
	
	static char[][] map;
	static int R, S;
	static List<Star> starList;
	static Star[] underStarList;
	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());
		S = Integer.parseInt(st.nextToken());
		
		map = new char[R][S];
		starList = new ArrayList<>(); // 전체 유성 리스트
		underStarList = new Star[S]; // 각 열의 유성 중 아래있는 유성 리스트
		
		// 입력 받기
		for(int i=0;i<R;i++) {
			String line = br.readLine();
			for(int j=0;j<S;j++) {
				map[i][j] = line.charAt(j);
				if(map[i][j] == 'X') {
					map[i][j] = '.'; // 맵에는 .로 초기화해서 맵에는 땅과 공기만 존재
					starList.add(new Star(i,j)); // X를 유성리스트에 저장
					underStarList[j] = new Star(i,j); // 0행부터 계속 각 열에 유성을 집어넣으면 결국 가장 아래의 유성을 저장하게 됨
				}
			}
		}
		
		
		
		
		// 땅에 부딪히거나 맵을 벗어나기 전까지 유성을 아래로 내림
		go(1);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<R;i++) {
			for(int j=0;j<S;j++) {
				sb.append(map[i][j]);
			}
			sb.append("\n");
		}
		
		System.out.print(sb);
		
	}
	
	static void go(int cnt) {
		boolean isCrash = false;
		for(Star star : underStarList) {
			// 땅에 부딪히거나 맵을 벗어나면
			if(star!=null && (star.r+cnt >= R || map[star.r+cnt][star.c] == '#')) {
				isCrash = true;
				break;
			}
		}
		
		// 부딪혔다면 부딪히기 직전인 현재 상태의 유성을 맵에 그림
		if(isCrash) {
			for(Star star : starList) {
				map[star.r+cnt-1][star.c] = 'X';
			}
		}
		// 현재 유성의 위치를 cnt만큼 내렸을 때 땅에 부딪히지 않고 맵을 벗어나지도 않는다면 cnt증가 
		else { 
			go(cnt+1);
		}
	}

}