BAEKJOON 7569
문제
입력
나의 처음 코드
이런 비슷한 문제를 풀어본 적이 있어서, 당연히 바로 맞을 줄 알았는데… 테케는 다 통과하는데 시간초과,,,, 하,,,증맬로다가,,, 일단 내가 생각했을 때는 시간초과가 익은 토마토만 담긴 dilic_tmt 리스트에서 pop할 때 나는 거로 추정한다. 왜냐하면 최대값이 100 x 100 x 100이니깐 백만인셈이기 때문이다. 시간 줄이는 장치로 tomato_cnt라는 변수를 설정해서 굳이 pop을 하지 않아도 끝날 수 있게 했다. 물론 시간 초과가 났지만,,, 코드는 다음과 같다.
# 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다.
# M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.
import sys
M, N, H = list(map(int, sys.stdin.readline().split()))
tmt_map = [[ ] for _ in range(H)]
dilic_tmt = []
tomato_cnt = 0 #나중에 다 바꿨을 떄, 토마토 총 갯수랑 비교해서 안 맞으면 모두 변하게 못한거임
#tmt_map에 토마토 담기 + 익은 토마토 좌표 dilic_tmt에 넣기
for stair in range(H):
for row in range(N):
tmp_list = list(map(int, sys.stdin.readline().split()))
tmt_map[stair].append(tmp_list)
for s in range(H):
for r in range(N):
for c in range(M):
if tmt_map[s][r][c] == 1:
dilic_tmt.append((0, s, r, c))
tomato_cnt += 1
if tmt_map[s][r][c] == -1:
tomato_cnt += 1
rl_side = [1, 0, -1, 0, 0, 0]
ud_side = [0, 1, 0, -1, 0, 0] #오른 아래 왼 위에
stair_updown = [0, 0, 0, 0, 1, -1] #위층 아래층
res = (N*M*H)
if tomato_cnt == res:
print(0)
else:
while dilic_tmt:
if tomato_cnt == res:
print(dilic_tmt[-1][0])
break
day, stair, row, col = dilic_tmt.pop(0) #(날, 층, 행, 열)
for i in range(6):
tmp_stair = stair + stair_updown[i]
tmp_row = row + ud_side[i]
tmp_col = col + rl_side[i]
if tmp_stair >= 0 and tmp_stair < H and tmp_row >= 0 and tmp_col >= 0 and tmp_row < N and tmp_col < M and tmt_map[tmp_stair][tmp_row][tmp_col] == 0:
tmt_map[tmp_stair][tmp_row][tmp_col] = 1
tomato_cnt += 1
dilic_tmt.append((day + 1, tmp_stair, tmp_row, tmp_col))
if tomato_cnt != res:
print(-1)
결과는 시간초과. 흠 로직은 맞는데 시간초과가 난다… 어디서 문제일까 생각해보면 당연히 제일 아래 while문이 아니겠거니,,, 하고 다른 사람들의 코드를 보니 다들 import를 해서 deque로 푸는 것이 아닌가? 나는 not import 맨임으로 그렇게 풀지 않겠다. 자 그러면 문제의 부분을 어떻게 수정해서 풀것인가? pop을 하지 말고 append만 하는 코드를 만들어보자!
개선된 코드
import sys
M, N, H = list(map(int, sys.stdin.readline().split()))
tmt_map = []
dilic_tmt = []
tomato_cnt = 0
for stair in range(H):
tmp = []
for row in range(N):
tmp_list = list(map(int, sys.stdin.readline().split()))
tmp.append(tmp_list)
tmt_map.append(tmp)
for s in range(H):
for r in range(N):
for c in range(M):
if tmt_map[s][r][c] == 1:
dilic_tmt.append((0, s, r, c))
tomato_cnt += 1
if tmt_map[s][r][c] == -1:
tomato_cnt += 1
rl_side = [1, 0, -1, 0, 0, 0]
ud_side = [0, 1, 0, -1, 0, 0] #오른 아래 왼 위에
stair_updown = [0, 0, 0, 0, 1, -1] #위층 아래층
res = (N*M*H)
if tomato_cnt == res:
print(0)
else:
while dilic_tmt:
if tomato_cnt == res:
print(dilic_tmt[-1][0])
break
tmp = []
#iteration으로 day별 익은 리스트를 넣는 것이다.
for day, stair, row, col in dilic_tmt:
for i in range(6):
tmp_stair = stair + stair_updown[i]
tmp_row = row + ud_side[i]
tmp_col = col + rl_side[i]
if tmp_stair >= 0 and tmp_stair < H and tmp_row >= 0 and tmp_col >= 0 and tmp_row < N and tmp_col < M and tmt_map[tmp_stair][tmp_row][tmp_col] == 0:
tmt_map[tmp_stair][tmp_row][tmp_col] = 1
tomato_cnt += 1
tmp.append((day+1, tmp_stair, tmp_row, tmp_col))
dilic_tmt = tmp
if tomato_cnt != res:
print(-1)
sys는 무시하고 아래 while문만 보도록 하자. 익은 토마토의 오왼아래위위층아래층을 보고 pop을 하는 방식이 아니라, day별로 리스트를 만들어서 iteration하는 방식을 쓰면 된다. 직관적으로 코드를 써놓았으니 보면 알것이다.
문제를 통한 플러스 씽킹
첫번째, 3차원 만드는 방식이다. 말하는 김에 2차원 만드는 방식을 써보겠다. 많이들 실수하는 2차원 만드는 방식은 다음과 같다.
a = 4 b = 3 dim_2 = [[0] * a] * b위와 같이 하면, 어떤 현상이 벌어지냐면, dim_2[0][1]을 고치면 dim[0~3][1]이 다 고쳐진다는 것이다. 한마디로 deep copy처럼 된다는 것이다. 그럼 어떻게 해야하냐? 2,3차원 둘다 알아보도록 하자.
a = 4 b = 3 c = 3 dim_2 = [[0] * a for _ in range(b)] dim_2 = [[[0] * a for _ in range(b)] for _ in range(c)]알다가도 모를 python 의 copy방식은 또 다른 곳에서 내 머리를 아프게 했다. 예를 들어, c++에서는 배열a = 배열b 하면 대부분 shallow copy가 된다. 하지만 파이썬은 다르다. 다음을 보도록 하자.
list_a = [1,2,3,4] list_b = [5,6,7,8] #1 tmp = list_a list_a[0] = 'a' #2 tmp = list_a list_a = [] tmp[0] = 'a'1번 같은 경우에는 list_a[0]을 바꾸면, tmp도 같이 바뀐다. 즉 deep copy가 된것이다.
2번의 경우에는 list_a = []로 리셋해줬기 때문에, tmp를 바꿔도 tmp만 바뀐다.
1번의 경우 해결하기 위해서는 대입할 때 copy() 함수를 같이 써주면 된다. 알다가도 모를 파이썬의 동작원리 ,,, 하하,,