백준 10703 유성 / python

문제 : 10703

풀이 point

유성의 모양이 흐트러지지 않고 제일 아래까지 움직여야 한다.

유성의 모양이 흐트러지지 않는 것을 판단하려면 X(유성 파편)가 #(바닥)을 처음 만났을 때의 가장 최소 값을 구하면 된다.

가장 최소 거리가 곧 유성의 모양이 흐트러지지 않고 제일 아래까지 움직일 수 있는 거리이다.

풀이 방법

각 열마다(세로) 조사를 하면서 X를 만나면 가장 마지막으로 만난 X의 위치를 갱신해주고, #을 만나면 현재 #(바닥) 위치 - 가장 마지막에 만난 X 위치 - 1(0인덱스)를 해주어 최소 거리를 갱신해준다. 모든 열에 대해 시행하여 가장 최소 거리를 구한다.

최소 거리를 구한뒤 최소 거리만큼 유성을 옮겨주면 된다.

풀이 코드

#백준, 10703 유성

R, S = map(int, input().split())

grid = [list(input()) for _ in range(R)]

def calcDist():
    minDist = R
    for i in range(S):
        dist = -9999
        for j in range(R):
            if grid[j][i] == 'X':
                dist = j
            elif grid[j][i] == '#':
                minDist = min(minDist, j-dist-1)
                break
    return minDist

minDist = calcDist()

for i in range(R-1, -1, -1):
    for j in range(S):
        if grid[i][j] == 'X':
            grid[i+minDist][j] = grid[i][j]
            grid[i][j] = '.'

for r in range(R):
    print(''.join(grid[r]))