10703 - 해결

유성

 

문제

작고 특이한 모양의 유성 사진이 인터넷에 올라왔다. 

사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다. 

유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 이를 복원해야 한다.

 

유성 사진을 문자의 배열로 단순화시켜 표기할 것이다. 문자 'X'는 유성의 일부를, 문자 '#'는 땅의 일부를, 

그리고 나머지(공기)는 문자 '.'로 이루어져 있다.

 

모든 유성 조각들은 연결되어 있다. 즉, 두 부분 유성이 존재한다면, 

한 쪽에서 유성 조각을 통해 상하좌우로 이동해서 다른 부분 유성에 도달할 수 있다. 

땅 또한 같은 방식으로 연결되어 있다.

 

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

유성은 그 보다 위에, 땅은 그 보다 아래쪽에 있다. 또한, 사진의 맨 밑 줄은 모두 땅이다.

유성은 수직으로 낙하한다. 유성이 땅에 떨어졌을 때, 유성과 땅은 원형을 유지한다고 한다. 

유성이 떨어진 후의 사진을 복구하여라.

 

입력

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

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

 

출력

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

---

일단 유성의 위치와 땅이 가장 가까운 곳을 찾고자한다.

수직으로 떨어진다고하니 일단 가장 적게 차이나는 곳 만큼 다 내려오면 거기서끝이기 때문에 

그런 방법으로 했을 때 땅이 높고 유성이 없을 경우

6 8
...X....
........
.......#
.......#
.......#
...#####
 
result:
........
........
.......#
.......#
...X...#
...#####

이 부분을 해결 하지 못해 ck_m을 추가 하였다.

 

하지만 22%를 못 넘어 간다. 왜지?

import sys

R, S = map(int,sys.stdin.readline().split())

pic = []
for _ in range(R):
    pic.append(list(sys.stdin.readline().strip()))

re_pic = []
for i in range(R):
    re_pic.append(list("".join(pic[i]).replace("X",".")))

min_air = R
for j in range(S):
    cnt = 0
    ck_m = False
    for i in range(R-1,-1,-1):
        if pic[i][j] == "X":
            ck_m = True
            break
        if pic[i][j] == ".":
            cnt += 1
    if min_air > cnt and ck_m:
        min_air = cnt


for j in range(S):
    for i in range(R):
        if pic[i][j] == "X":
            re_pic[i+min_air][j] = "X"

for i in range(R):
    print("".join(re_pic[i]))

답이라고 올라온거도 시간 초과... 이게 뭐지 ㅇㅅㅇ 

그리고 22%에서 계속 실패하길래 여러 반례를 찾아보다가 찾은 것이

 

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

result:
.........
.........
..XXXX...
..X######
..X.....#
..X.....#
..XXXX..#
##.....##
#########

이 케이스 중간에 땅이 있는 경우 내가 한 방법으로 하면 최소거리가 2라서 잘못된 경우가 나온다. 그래서 X일 때 break하는 것이 아닌 전체 부분을 다 탐색하는 방법을 사용하고자 하였다.

 

import sys

R, S = map(int,sys.stdin.readline().split())

# 사진 저장
pic = [input() for _ in range(R)]  

# 복원할 사진 유성부분을 공기로 바꾼다.
re_pic = []
for i in range(R):
    re_pic.append(list("".join(pic[i]).replace("X",".")))

# 가장 길때가 아무리 길어도 세로길이 보다 짧을 테니 R로 설정
min_air = R
# 세로 줄로 확인
for j in range(S):
    cnt = 0
    ck_m = False
    # 최소 거리 확인하기
    # 밑에 부터 확인하여 공기 층을 세리고 유성을 만나면 공기 층이 몇개인지 판단하고 
    for i in range(R-1,-1,-1):
        # 밑에 부터 유성을 만나면 거리를 측정한다.
        if pic[i][j] == "X":
            ck_m = True
            if min_air > cnt and ck_m:
                min_air = cnt
        # 공기 층이 나오면 cnt를 세린다.
        elif pic[i][j] == ".":
            cnt += 1
        # 중간에 땅이 나오는 걸 대비하여 
        elif pic[i][j] == "#":
            cnt = 0
    
    # 왜 이걸 빼면 시간 초과가 날까?
    if min_air > cnt and ck_m:
        min_air = cnt

# 복원 사진을 위해 X를 만나면 최소 거리만큼 이동
for j in range(S):
    for i in range(R):
        if pic[i][j] == "X":
            re_pic[i+min_air][j] = "X"

for i in range(R):    # 결과 출력
    print("".join(re_pic[i]))