이 문제는 실온에 둔 치즈가 있고,
공기를 접한 치즈 부분은 정확히 한시간 후에 사라진다고 가정했을 때,
치즈의 모든 부분이 녹아 없어지는게 걸리는 정확한 시간을 구하는 프로그램을 작성해야 한다.
문제 풀이
공기에 닿은 치즈인지를 구분하는 방법을 찾는게 문제 풀이의 관건이다. 공기와 밀접한 치즈의 경우에는 얼마나 많은 면이 공기와 맞닿아 있는지 치즈에 수치를 적어준다. 수치가 2이상인 치즈와 맞닿아 있는 치즈인 경우에는 직접적으로 공기와 닿진 않지만 간접적으로 공기와 닿아있는 것과 같다. 치즈를 다 녹인 다음에는 다시 수치를 측정하기 위해서 치즈의 수치를 본래 값으로 변경해주어야 한다.
파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
import sys
import copy
direction = [(0,1),(1,0),(0,-1),(-1,0)]
def solve(n, m, array):
time = 0
while True:
checkCheese(n, m, array)
extraCount = meltDown(n, m, array)
time += 1
if extraCount == 0:
array = None
return time
def checkCheese(n, m, array):
queue = []
queue.append((0,0))
while queue:
pos = queue.pop(0)
i = pos[0]
j = pos[1]
if array[i][j] == 0:
array[i][j] = -1
for case in direction:
next_i = i + case[0]
next_j = j + case[1]
if next_i > -1 and next_j > -1 and next_i < n and next_j < m:
next_value = array[next_i][next_j]
if next_value > 0:
array[next_i][next_j] += 1
elif next_value == 0:
queue.append((next_i, next_j))
def meltDown(n, m, array):
extraCheeseCount = 0
for i in range(n):
for j in range(m):
current_value = array[i][j]
# 남은 치즈의 수
if current_value == 1 or current_value == 2:
extraCheeseCount += 1
array[i][j] = 1
# 공기와 2 이상 밀접한 치즈를 녹이거나 공기를 -1 => 0으로 바꿔준다
if current_value == -1 or current_value > 2:
array[i][j] = 0
return extraCheeseCount
if __name__ == "__main__":
n, m = sys.stdin.readline().strip().split()
array = []
for i in range(int(n)):
line = list(map(int,sys.stdin.readline().strip().split()))
array.append(line)
print(solve(int(n), int(m), array))
|
cs |
'온라인 코딩 테스트 문제 풀이 > 백준 문제 풀이' 카테고리의 다른 글
Python으로 푸는 백준 9012. 괄호 (0) | 2019.04.17 |
---|---|
Python으로 푸는 백준 3184. 양 (0) | 2019.04.12 |
Python으로 푸는 백준 16235. 나무 재테크 (1) | 2019.03.25 |
python으로 푸는 백준 14890. 경사로 (0) | 2019.03.22 |