[Python/파이썬] 백준 10703번 유성

 

10703번: 유성

 

문제

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

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

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

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

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

입력

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

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

출력

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

코드

import sys
input = sys.stdin.readline

r, s = map(int, input().split())
picture = []
max_meteor = [-3000] * s
min_ground = [r-1] * s
for i in range(r):
    picture.append(input())
    for j in range(s):
        if picture[i][j] == 'X':
            max_meteor[j] = max(max_meteor[j], i)
        elif picture[i][j] == '#':
            min_ground[j] = min(min_ground[j], i)
min_air = 3000
for j in range(s):
    if min_air > (min_ground[j]-max_meteor[j]-1):
        min_air = (min_ground[j]-max_meteor[j]-1)

res = [['.']*s for _ in range(r)]

# 유성 떨어져
for i in range(r):
    for j in range(s):
        if picture[i][j] == 'X':
            res[i+min_air][j] = 'X'
        elif picture[i][j] == '#':
            res[i][j] = '#'

# 사진 출력
for i in range(r):
    for j in range(s):
        print(res[i][j], end='')
    print()

PyPy3로는 바로 통과가 됐는데 Python3로는 계속 수정해봐도 시간 초과로 통과가 안된다....

다른 사람들은 파이썬으로 어떻게 했는지 찾아보니까 출력문을 print가 아니라 sys.stdout.write로 쓰는 등 실행 속도가 빠른 출력문으로 바꿔주는 정도의 차이 밖에 없는 것 같아서 그냥 냅뒀다.