[Java] 백준 10703 유성

hyunnzl·2025년 7월 7일

algorithm

백준

목록 보기

101/116

https://www.acmicpc.net/problem/10703

난이도

실버 1

문제

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

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

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

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

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

입력

첫 번째 줄에는 각각 사진의 세로와 가로 길이를 의미하는 정수 R과 S (3 ≤ R, S ≤ 3 000)가 주어진다.

다음 R 개의 줄에는 문자로 단순화된 사진이 주어진다.

출력

유성이 떨어지고 난 뒤의 사진(크기 R × S)을 복원하여 출력하라.

코드

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];
        for(int i = 0; i < N; i++){
            String line = br.readLine();
            map[i] = line.toCharArray();
        }

        int down = N;
        for (int col = 0; col < M; col++) {
            int maxX = -1;
        
            for (int row = 0; row < N; row++) {
                if (map[row][col] == 'X') {
                    maxX = row;
                } else if (map[row][col] == '#') {
                    if(maxX == -1) continue;
                    down = Math.min(down, row - maxX - 1);
                    break;
                }
            }
        }

        List<int[]> stars = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'X') {
                    stars.add(new int[]{i, j});
                }
            }
        }

        for (int[] s : stars) {
            map[s[0]][s[1]] = '.';
        }

        for (int[] s : stars) {
            int newRow = s[0] + down;
            if (newRow < N) {
                map[newRow][s[1]] = 'X';
            }
        }
  
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(map[i]).append('\n');
        }
        System.out.print(sb);
    }

}