[알고리즘 잡스 / CHEEZE 문제]
문제 해석
: 치즈와 치즈가 놓여진 판이 주어진다. 판 위에 치즈가 놓인 정보를 바탕(2차원 배열)으로 치즈가 '공기와 닿는' 부분을 1시간 마다 없애면서 치즈가 모두 없어지기 까지 몇시간이 걸리고, 마지막 없어지기 1시간 전의 판위의 치즈가 차지하는 칸 수를 리턴하면 되는 문제. 이 때, 주의할 점은 공기와 닿는 면만 녹는다는 것이다. 치즈 안에는 구멍이 있는데 이 구멍 안에는 공기가 없다는 전제이다. 물론 치즈가 녹으면서 구멍과 바깥 사이에 틈이 생기면 그 때부터는 거기에 공기가 들어가서 그 부분도 녹는다는 설정이다. 사실 문제를 풀 때 이부분을 간과하고 0과 닿는 부분은 모두 녹는 설정으로 멋대로(?).. 문제를 풀어서 초반에 조금 헤맸다.
문제 설계 및 해결책
: 치즈를 갉아먹는(?) 공기를 어떻게 구현할까에 초점을 맞춰보면, 공기는 치즈를 겉면부터 녹인다에 포인트를 맞춰야한다. 처음에는 치즈를 기준으로 탐색을 하면서 겉면만 탐색하는 방법이 없을까? 라는 생각을 했지만, 관점을 바꿔서 공기의 입장(?)에서 탐색을 해야한다고 생각했다. 공기의 입장에서 자신의 주변에 있는 치즈를 녹이고, 그 부분부터는 탐색을 멈추는 방향으로 풀어보는 것이다. 달리 말해, (1,1) 노드(공기의 위치 중 하나)를 기준으로 BFS를 한다고 생각하면, 모든 공기를 BFS로 탐색할 것이다. 탐색을 하다보면 공기 노드의 자식노드에는 분명히 치즈노드가 있을 것이다. 그 치즈 노드를 발견하면 무조건 제거한다. 하지만, 그 치즈 노드의 자식노드로는 탐색을 멈춰야한다. 그 치즈의 자식 노드까지 탐색을 하면 한시간에 공기와 닿는 면적 중 1부분만 제거된다는 룰이 위반된다. 이런식으로 한시간마다. 치즈가 놓인 판 전체를 탐색하면서(공기 노드를 시작으로), 공기와 닿는 치즈를 하나만 없애고 더이상 그쪽으로 탐색을 멈추는 방식으로 진행하면 공기가 치즈를 한시간마다 겉면만 녹이는 것을 구현할 수 있다. 이렇게하면 겉면만 녹이고 멈추기 때문에 치즈 안에 구멍이 있는 경우에도 그 안에를 탐색하지 않기 때문에 문제가 없다.
구현 설계
: 내가 짠 로직대로 풀기 위해서는 먼저 0을 찾아야한다. 즉, 루트 공기 노드를 하나 정해야하므로 O(N)의 시간복잡도로 0을 찾고 해당 좌표를 저장하고 break 한다. 그러면 그 루트 공기 노드를 가지고 BFS 탐색을 시작한다. 이 때, 조건은 위에서 말한대로
- 공기를 만나면 그 공기를 방문했다는 기록을 저장해두고 그 공기의 자식 노드를 큐에 새로 넣고, 방금 탐색한 공기는 pop
- 치즈를 만나면 그 치즈를 제거하고, 더이상 그곳을 방문하면 안되므로 역시 해당 좌표를 방문했음을 기록하고 pop한다(큐에 넣지 않음).
- 이런식으로 BFS를 진행하는데 이러한 BFS를 치즈가 모두 녹을 때까지(while) 진행해야한다. 즉, 이중 while문으로 구현하면서 두번째 While문으로 BFS를 구현한다. 그러면서 첫번째 While문에서 몇시간이 지났는지를 카운트한다. 이 때, BFS가 끝나고 prev라는 변수에 이전에 치즈 개수를 저장해두면서 진행해야만 마지막에 남은 치즈를 구할 수 있다.
위의 방법으로 하면 시간복잡도에는 문제가 없을까? 일단 가로, 세로의 최대값은 100이다. 내가 만든 로직대로라면 치즈가 모두 없어질 때까지 100*100 = 10000번의 BFS 시행을 하고, 이 시행을 치즈가 모두 녹을 때까지 진행한다. 하지만 최악의 경우 치즈가 판 전체를 차지해서 풀 시행(?)을 해야한다 할 때, 한번에 테두리를 없애면서 진행하기 때문에 시간복잡도에 영향을 미칠 정도로 큰 회수로 진행하지는 않게 된다.
** 이전의 치즈 개수를 시행이 끝날 때마다 다 세어보는건 좀 비효율적인 것 같고 처음에 0을 찾을 때나, 처음 board를 만들 때 1의 개수를 세어놓고, 치즈를 지울 때마다 카운트를 해서 그 개수에서 빼면서 나아가면 될 것 같다.
구현 코드(1)
import copy
n,m = map(int, input().split())
board = []
for i in range(n):
board.append([-1] + list(map(int, input().split())) + [-1])
board = [[-1 for i in range(m+2)]] + board + [[-1 for i in range(m+2)]]
cnt = 0
while True:
cnt+= 1
copy_board = copy.deepcopy(board)
path = {}
queue = [(1,1)]
path[(1,1)] = True
deleted_count = 0
while len(queue) != 0 :
top = queue.pop(0)
up = (top[0]-1, top[1])
right = (top[0], top[1]+1)
down = (top[0]+1, top[1])
left = (top[0], top[1]-1)
arr = []
if board[up[0]][up[1]] == -1:
pass
elif board[up[0]][up[1]] == 0:
try:
if path[up]:
pass
except:
path[up] = True
arr.append(up)
elif board[up[0]][up[1]] == 1:
try:
if path[up]:
pass
except:
path[up] = True
copy_board[up[0]][up[1]] = 0
deleted_count+=1
if board[right[0]][right[1]] == -1:
pass
elif board[right[0]][right[1]] == 0:
try:
if path[right]:
pass
except:
path[right] = True
arr.append(right)
elif board[right[0]][right[1]] == 1:
try:
if path[right]:
pass
except:
path[right] = True
copy_board[right[0]][right[1]] = 0
deleted_count+=1
if board[down[0]][down[1]] == -1:
pass
elif board[down[0]][down[1]] == 0:
try:
if path[down]:
pass
except:
path[down] = True
arr.append(down)
elif board[down[0]][down[1]] == 1 :
try:
if path[down]:
pass
except:
path[down] = True
copy_board[down[0]][down[1]] = 0
deleted_count+=1
if board[left[0]][left[1]] == -1:
pass
elif board[left[0]][left[1]] == 0:
try:
if path[left]:
pass
except:
path[left] = True
arr.append(left)
elif board[left[0]][left[1]] == 1:
try:
if path[left]:
pass
except:
path[left] = True
copy_board[left[0]][left[1]] = 0
deleted_count+=1
queue+= arr
flag = True
for i,row in enumerate(copy_board):
for j, col in enumerate(row):
if col == 1 :
flag = False
board[i][j] = col
if flag:
print(cnt)
print(deleted_count)
break
: 위의 코드가 내가 이 블로그 포스팅을 하기 전에 문제를 풀 때 썼던 코드이다. 하지만, 좀 더 효율적으로 코드를 짜보는겸(?) 복습겸 문제를 다시 풀어봤다.
구현 코드(2)
n, m = map(int, input().split())
board = []
root = ()
cheese_cnt = 0
flag = True
for i in range(n):
input_list = list(map(int, input().split()))
if 0 in input_list and flag:
root = (i+1, input_list.index(0)+1)
flag = False
cheese_cnt += input_list.count(1)
board.append([None] + input_list + [None])
limit_line = [[None for i in range(m+2)]]
board = limit_line + board + limit_line
hour = 0
if cheese_cnt == 0:
print(hour)
else:
queue = []
prev_cnt = cheese_cnt
while True:
hour += 1
queue.append(root)
visit = {}
visit[root] = True
while len(queue) != 0:
top = queue.pop(0)
ways = [(top[0]-1,top[1]),(top[0],top[1]+1),(top[0]+1,top[1]),(top[0],top[1]-1)]
for dir in ways:
if board[dir[0]][dir[1]] is None:
continue
else:
try:
if visit[dir]:
continue
except:
visit[dir] = True
if board[dir[0]][dir[1]] == 1:
cheese_cnt -= 1
board[dir[0]][dir[1]] = 0
elif board[dir[0]][dir[1]] == 0:
queue.append(dir)
if cheese_cnt == 0:
break
prev_cnt = cheese_cnt
print(hour)
print(prev_cnt)
좀 더 효율적인 코드를 짰다기보다 그래도 이전보다는 간소화됐고, 더 간단한 로직으로 짰다. 확실히 처음에는 deepcopy를 이용해서 board를 계속해서 복사해가면서 체크를 했는데 굳이 왜그랬나 싶다. 또한, 첫 번째 시도에서는 if문을 여러개 써서 코드의 길이가 쓸데없이 길어졌는데, 두 번째에서는 그 부분을 많이 간소화시켰다. 그리고 이전 코드에서는 매시행마다 치즈가 다 녹았는지 확인하기 위해 전체 배열을 다 훑었는데, 이번에는 cheese_cnt를 이용해서 그런 비효율성을 뺐다.
