[Python] 백준 10703: 유성

solved.ac 기준 Silver 1

 

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1 

5 6
.XXXX.
...X..
......
#..###
######

예제 출력 1 

......
.XXXX.
...X..
#..###
######

예제 입력 2 

9 7
XXX.XXX
X.XXX.X
X..X..X
X.....X
.......
.#...#.
.##.##.
.#####.
#######

예제 출력 2

.......
.......
.......
.......
XXX.XXX
X#XXX#X
X##X##X
X#####X
#######

 

정답 코드

R, S = map(int, input().split())
pic = [list(input()) for _ in range(R)]

stars_for_draw = []

# 열 별로 가장 낮은 위치의 별 저장
stars = [-1] * S
# 열 별로 가장 높은 위치의 땅 저장
ground = [R] * S

for i in range(R):
    for j in range(S):
        if pic[i][j] == 'X':
            pic[i][j] = '.'
            stars[j] = max(i, stars[j])
            stars_for_draw.append((i, j))
        if pic[i][j] == '#':
            ground[j] = min(i, ground[j])

min_height = 3000
for i in range(S):
    if stars[i] == -1:
        continue
    min_height = min(min_height, ground[i] - stars[i] - 1)

for x, y in stars_for_draw:
    pic[x + min_height][y] = 'X'

for p in pic:
    print(''.join(p))

 

 단순하게 생각하여 총 세 가지의 방법을 거치며 문제를 풀게 되었다.

 

 첫 번째. 별들의 좌표를 전부 저장하여 반복문을 통해 한 칸 씩 내리는 방법으로 문제를 풀었으나, 메모리 초과가 났다. 3000*3000을 반복하기 때문에 최악의 경우에는 900만개가 넘을 수 있다. 그러므로 큐를 쓰든 뭐를 쓰든 메모리 한계에 도달할 수 밖에 없다.

 

 두 번째. 별들의 좌표를 전부 저장한 후, 별부터 땅 까지의 거리 중 가장 최소가 되는 거리를 구했다. 이 또한 반복문을 통해서 했는데, 별의 개수가 너무 많을 수 있는 것을 간과했다. 시간 초과로 실패.

 

 세 번째. 각 열 별로 가장 낮은 별의 좌표와 가장 높은 땅의 좌표를 저장하고, 그 차이가 최소가 되는 값을 찾아내 한 번에 옮겼다. 시간 복잡도를 확실히 줄일 수 있었다. 또한 여기에서도 50%에서 에러가 났는데, 그 이유는 땅은 무조건 존재할 수 있지만 별은 없는 열이 있는 것을 간과하고 예외처리를 하지 않았기 때문에다. 성공