[알고리즘 잡스 / TOMATO 문제] 
: 이 문제는 처음에는 시간복잡도를 잘못 예측해서 완전 탐색으로 풀었던 문제이다. 하지만, 결국 시간복잡도에서 걸려서 다른 방향으로 생각해서 풀어낸 문제.
완전탐색으로 풀었던 코드
완전탐색 풀이
boxes = {}
for floor in range(h):
box = []
for i in range(n):
row = [None]+list(map(int, input().split()))+[None]
box.append(row)
boxes[floor] = [[None for j in range(m+2)]]+box+[[None for j in range(m+2)]]
# boxes 만들기 clear
# 이제 이 박스를 하나하나 탐색해야함 완전탐색을 쓸 것
day = 0
prev_count = -1
while True:
zero_count = 0
copy_boxes = {}
for floor in range(h):
box = boxes[floor]
copy_box = []
for i in range(1,n+1):
arr = [None]+[0 for k in range(m)]+[None]
for j in range(1,m+1):
arr[j] = box[i][j]
if box[i][j] == 0:
zero_count+=1
copy_box.append(arr)
copy_box = [[None for k in range(m+2)]]+copy_box+[[None for k in range(m+2)]]
copy_boxes[floor] = copy_box
if zero_count == 0:
print(0)
break
day+= 1
for floor in range(h):
box = boxes[floor]
# 0층부터 탐색할 것
for i in range(1,n+1):
for j in range(1,m+1):
if box[i][j] == 0 or box[i][j] == -1 :
continue
else:
try:
if copy_boxes[floor-1][i][j] == 0:
copy_boxes[floor-1][i][j] = 1
except:
pass
try:
if copy_boxes[floor+1][i][j] == 0:
copy_boxes[floor+1][i][j] = 1
except:
pass
# 3차원에서 아래 위를 익게 만들고
# 2차원에서 위아래왼쪽 오른쪽을 익게 만들기
if copy_boxes[floor][i-1][j] == 0:
copy_boxes[floor][i-1][j]=1
if copy_boxes[floor][i+1][j] == 0:
copy_boxes[floor][i+1][j]=1
if copy_boxes[floor][i][j-1] == 0:
copy_boxes[floor][i][j-1]=1
if copy_boxes[floor][i][j+1] == 0:
copy_boxes[floor][i][j+1]=1
boxes = {}
zero_count = 0
for floor in range(h):
box = copy_boxes[floor]
new_box = []
for i in range(1,n+1):
arr = [None]+[0 for k in range(m)]+[None]
for j in range(1,m+1):
arr[j] = box[i][j]
if box[i][j] == 0:
zero_count+=1
new_box.append(arr)
new_box = [[None for k in range(m+2)]]+new_box+[[None for k in range(m+2)]]
boxes[floor] = new_box
if prev_count == zero_count:
print(-1)
break
prev_count = zero_count
if zero_count == 0 :
print(day)
break
문제 해석
: 토마토를 담는 프레임이 있고, 그 프레임을 쌓아서 토마토를 관리하는데, 이 때, 주술적인 규칙(?)은 익은 토마토 주변의 토마토들은 하루가 지나면 익은 토마토의 영향을 받아서 똑같이 익게 된다는 것이다. 이 원리를 바탕으로 1차원 프레임을 3차원으로 쌓아올린 토마토 보관소에서 모든 토마토가 익으려면 최소 몇일이 걸리는지를 구해야하는 문제이다. 이 때, 토마토가 없는 빈곳이 있을 수 있고, 익은 토마토의 주술적인 범위는 동서남북, 위아래 이렇게 6방향으로 이뤄진다.
문제 설계 및 해결책
: 토마토가 들어있는 프레임 정보가 층수대로 0층부터 주어지고, 그 정보에는 1번이 익은 토마토, 0번이 익지 않은 토마토, -1이 아무것도 없는 것을 의미한다. 그러면 포인트는 익은 토마토를 기준으로 익지 않은 토마토를 익게 만드는 것인데, 익은 토마토를 기준으로 '익게 만드는' 혹은 '익은 상태'가 퍼져나가는 원리를 생각해보면 그래프에서 루트 노드를 기준으로 자식노드로 전파(혹은 전염같은 것을 생각하기)되는 원리와 비슷한 것을 떠올려야한다. 익은 토마토를 기준으로 위아래, 동서남북의 자식 노드가 0번(익지 않은 토마토)이라면 그 모두를 1번으로 만들고(하루가 지났고), 이제는 새로 1번으로 만든 노드들을 기준으로 또다시 그 자식 노드를 1번으로 만들고(또 하루가 지난다), 이런식으로 퍼져나가는 그림을 생각해보면, 결국 루트 노드를 기준으로 Breadth-First-Search(BFS)하는 것과 같다는 것을 떠올릴 수 있다. 이 때, 몇일이 걸릴지 모르니 BFS를 여러번 시행해야한다. 그렇게 계속해서 BFS를 시행하다가 모든 토마토가 1이되면 끝이나고, 만약 빈칸 때문에 퍼지지 못하는 영역이 존재한다면 -1을 리턴해야하는 부분이 걸리게 되는데, 이 부분을 컨트롤하기 위해 시행마다 익게한 토마토의 개수를 세서 만약 0이면 break 걸도록 한다. 그래서 더이상 0이 없으면 익는데 걸린 날을 리턴하고, 0이 있으면 -1을 리턴하면 된다.
구현 설계
: 처음에 익은 토마토를 큐에 담아서 그 익은 토마토를 기준으로 BFS를 시작한다. 익은 토마토에서 익게할 수 있는 토마토 목록을 구하고, 그 목록을 다음 시행을 위해 큐에 넣는다(동시에 이미 익어있던 루트 노드가 되는 토마토는 pop해줘야한다. 더이상 필요가 없으니). 그리고 추가하면서 익게한 토마토의 개수를 센다. 이렇게 생각하면 별 무리없이 구현할 수 있을 것 같은데 여기서 약간 독특한 점은 3차원적인 생각이 필요하다는 것이다. 여태까지는 동서남북만 검색하면 되는 문제들만 풀었는데, 여기서는 위아래까지 더해진다. 따라서 이 3차원 개념의 탐색을 가능하게 하려면, 층개념을 추가해야한다. 그래서 나는 이 층개념을 파이썬 딕셔너리로 구현하고자 한다. 그래서 익은 토마토를 기준으로 현재층-1, 현재층+1, 현재위치에서 동서남북 이렇게 6방향으로 익게하는 로직을 만들 것이다. 이 때, 딕셔너리에서는 key가 없는데 참조하면 error를 리턴하므로 에러처리를 해주고, 이미 들른 곳이라면 들르지 않는 로직도 만들어줘야한다. 추가로 -1 혹은 이미 익은 곳이면 패스하는 로직도 만들어야하고!. 1차원에서는 경계처리를 해서 프레임을 벗어나는 지역을 탐색해도 에러가 나지 않으면서 그곳은 탐색 안하도록 해야한다.
구현 코드(1)
import copy
m, n, h = map(int, input().split())
# BFS 풀이
boxes = {}
for floor in range(h):
box = []
for i in range(n):
row = [-1]+list(map(int, input().split()))+[-1]
box.append(row)
boxes[floor] = [[-1 for j in range(m+2)]]+box+[[-1 for j in range(m+2)]]
queue = []
zero_count = 0
for key,box in boxes.items():
for i, stage in enumerate(box):
if i == 0 or i == len(box)-1:
continue
for j, val in enumerate(stage):
if val == 1:
queue.append((key,i,j))
elif val == 0:
zero_count += 1
day = 0
if zero_count == 0 :
print(0)
else:
path = {}
while len(queue) != 0:
day += 1
new_arr = []
for top in queue:
floor = top[0]
indx = (top[1],top[2])
path[top] = True
try:
if boxes[floor-1][indx[0]][indx[1]] == 0:
try:
if path[(floor-1, indx[0],indx[1])]:
pass
except:
boxes[floor-1][indx[0]][indx[1]] = 1
path[(floor-1, indx[0],indx[1])] = True
new_arr.append((floor-1, indx[0],indx[1]))
except:
pass
try:
if boxes[floor+1][indx[0]][indx[1]] == 0:
try:
if path[(floor+1, indx[0],indx[1])] :
pass
except:
path[(floor+1, indx[0],indx[1])] = True
boxes[floor+1][indx[0]][indx[1]] = 1
new_arr.append((floor+1, indx[0],indx[1]))
except:
pass
if boxes[floor][indx[0]-1][indx[1]] == 0:
try:
if path[(floor, indx[0]-1,indx[1])]:
pass
except:
path[(floor, indx[0]-1,indx[1])] = True
boxes[floor][indx[0]-1][indx[1]] = 1
new_arr.append((floor, indx[0]-1,indx[1]))
if boxes[floor][indx[0]+1][indx[1]] == 0:
try:
if path[(floor, indx[0]+1,indx[1])]:
pass
except:
path[(floor, indx[0]+1,indx[1])] = True
boxes[floor][indx[0]+1][indx[1]] = 1
new_arr.append((floor, indx[0]+1,indx[1]))
if boxes[floor][indx[0]][indx[1]-1] == 0:
try:
if path[(floor, indx[0],indx[1]-1)] :
pass
except:
path[(floor, indx[0],indx[1]-1)] = True
boxes[floor][indx[0]][indx[1]-1] = 1
new_arr.append((floor, indx[0],indx[1]-1))
if boxes[floor][indx[0]][indx[1]+1] == 0:
try:
if path[(floor, indx[0],indx[1]+1)]:
pass
except:
path[(floor, indx[0],indx[1]+1)] = True
boxes[floor][indx[0]][indx[1]+1] = 1
new_arr.append((floor, indx[0],indx[1]+1))
queue = new_arr
zero_count = 0
for floor in list(boxes.keys()):
for i in range(1, n+1):
for j in range(1, m+1):
if boxes[floor][i][j] == 0 :
zero_count+= 1
if zero_count == 0:
print(day-1)
else:
print(-1)
위 코드가 문제를 처음 풀어볼 때 썼던 코드이다.
구현 코드(2)
m, n, h = map(int, input().split())
done_cnt = 0
not_done_cnt = 0
tower = {}
queue = []
for floor in range(1,h+1):
tower[floor] = []
tower[floor].append([[-1 for k in range(m+2)]])
for i in range(n):
input_list = list(map(int, input().split()))
row = [-1]+input_list+[-1]
for idx,el in enumerate(input_list):
if el == 1 :
queue.append((floor, i+1, idx+1))
done_cnt+= 1
elif el == 0:
not_done_cnt+= 1
tower[floor].append(row)
tower[floor].append([[-1 for k in range(m+2)]])
def get_value(t) :
global tower
try:
result = tower[t[0]][t[1]][t[2]]
if result == 0:
tower[t[0]][t[1]][t[2]] = 1
return 1
elif result == -1 :
return -1
elif result == 1 :
return -1
except:
result = -1
return result
if not_done_cnt == 0:
print(0)
else:
days = 0
while len(queue) != 0 :
days+= 1
next_queue = []
for tomato in queue:
ways = [(tomato[0]-1,tomato[1],tomato[2]),(tomato[0]+1,tomato[1],tomato[2]),(tomato[0],tomato[1]-1,tomato[2]),(tomato[0], tomato[1]+1,tomato[2]),(tomato[0],tomato[1],tomato[2]-1),(tomato[0],tomato[1],tomato[2]+1)]
for dir in ways:
if get_value(dir) == -1 :
continue
else:
not_done_cnt -= 1
next_queue.append(dir)
if not_done_cnt == 0:
print(days)
break
queue = next_queue
if len(queue) == 0:
print(-1)
break
: 함수를 만들어서 코드를 좀더 간소화시켜봤다. 이런식으로 함수를 만들어서 은닉화하는 방법을 좀 더 응용할 수 있어야겠다.
