유성
문제
작고 특이한 모양의 유성 사진이 인터넷에 올라왔다.
사진에는 매우 높은 곳에서 떨어지고 있는 유성이 허공에 찍혀 있었다.
유성이 떨어지고 난 뒤의 사진도 있었지만 안타깝게도 소실돼버려 이를 복원해야 한다.
유성 사진을 문자의 배열로 단순화시켜 표기할 것이다. 문자 '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]))
'@@@ 알고리즘 > 백준 스터디' 카테고리의 다른 글
18222 - 메모리 초과 - 해답 (0) | 2021.08.01 |
---|---|
7569 - 답 확인 (0) | 2021.08.01 |
15903 - 해결 (0) | 2021.07.31 |
1535 - 해결 (0) | 2021.07.31 |
1931 (0) | 2021.07.30 |