[백준] 10703번 : 유성 (C++)

10703번 : 유성

---

문제)

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

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

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

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

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

 

 

 

입력 :

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

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

 

 

 

출력 :

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

 

 

 

 

 

풀이)

 

// 10703. 유성
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int n, m;
vector<string> vec;
 
int diff()
{
    int top = 0;
    int btm = 0;
 
    // 세로를 기준으로 유성과 땅의 거리 중 제일 작은 값을 찾는다.
    int down = 9999;
    for (int i = 0; i < m; i++)
    {
        top = 9999;
        btm = 9999;
        for (int j = 0; j < n; j++)
        {
            if (vec[j][i] == 'X')
            {
                top = j;
            }
 
            if (vec[j][i] == '#')
            {
                btm = j;
                break;
            }
        }
        
        // 유성이나 땅이 없는 세로 줄이 있을 수 있으므로
        // 예외처리
        if (abs(top - btm) >= 1)
        {
            down = min(down, abs(btm - top) - 1);
        }
    }
 
    // 땅과 유성의 최소 거리를 반환한다.
    return down;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
 
    // 입력 받기
    string temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        vec.push_back(temp);
    }
 
 
    int d = diff();
 
    // 새로운 지도를 그릴 새 배열
    vector<vector<char>> temp_map(n, vector<char> (m, '0'));
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // 유성인 경우 d 만큼 내려 그리고
            if (vec[i][j] == 'X')
            {
                temp_map[i + d][j] = 'X';
            }
            // 땅은 그대로 그린다.
            else if (vec[i][j] == '#')
            {
                temp_map[i][j] = '#';
            }
            // 나머지는 빈 공간인 0으로 채워져 있음.
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            // 빈 공간인 경우 공기를 출력하고
            if (temp_map[i][j] == '0') cout << '.';
            // 유성과 땅을 출력해준다.
            else cout << temp_map[i][j];
        }
        cout << "\n";
    }
    
    return 0;
}
 
 
 

---

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

10703번: 유성