[구름LEVEL 유형 트레이닝 / 구현] 단풍나무 (python)

풀이

import copy

N = int(input())
park = [0 for _ in range(N)]

for i in range(N):
	park[i] = list(map(int, input().split()))

present_park = copy.deepcopy(park)
	
day = 0
d = [[-1, 0], [1, 0], [0, -1], [0, 1]] # 상하좌우

	
while True:
	park = copy.deepcopy(present_park)
	all_maple = True
    
	for i in range(N):
		for j in range(N):
			if park[i][j] != 0:
				all_maple = False
				break
		if not all_maple:
			break
	
	if all_maple:
		print(day)
		break
		
	day += 1
    
	for i in range(N):
		for j in range(N):
			maple_cnt = 0
			
			if park[i][j] == 0:
				continue
		
			for k in range(4):
				x = j + d[k][1]
				y = i + d[k][0]

				if x < 0 or x > N - 1 or y < 0 or y > N - 1:
					continue
                    
				if park[y][x] == 0:
					maple_cnt += 1

			present_park[i][j] -= maple_cnt
			
			if present_park[i][j] < 0:
				present_park[i][j] = 0

park 변수에 단풍나무의 상태를 2차원 배열로 저장했다.

day 변수는 모든 구역에 단풍이 물들기까지 걸리는 시간을 의미한다.

d는 한 구역의 인접한 구역을 살피기 위한 상하좌우를 나타내는 방향이다.  

 

park 배열 전체를 돌면서 우선 전체 구역에 단풍이 물들었는지를 먼저 확인한다.

아니라면, 다시 park 전체를 돌면서 인접한 구역에 단풍이 들었는지, 그래서 내 구역의 단풍이 얼만큼 물들 수 있는지를 maple_cnt 에 저장한다. 인접 구역의 위치는 (x, y)로 나타낸다.

maple_cnt 만큼을 빼주는데, 이때 park 배열은 건드리지 않고 park를 복사한 present_park에서 빼준다.(하나의 day가 지나고 park 전체에 변화가 있어야 하기 때문이다. 복사하지 않고 변경하면 답이 다르게 나온다.)

 

위 과정을 반복하면 모든 단풍이 물들었을 때의 day를 알 수 있다.

 

 

 

제출 하면서 다른 테스트 케이스는 다 통과했는데 하나가 통과되지 않아 막혔었다.

뭘까 했는데 애초부터 모든 구역에 단풍이 물들었을 경우, day가 0이어야 하는 부분을 간과한 게 실수였다. 이전 코드는 while문 시작부터 day += 1을 하고, 마지막에 모든 단풍이 물들었는지를 검사해서 단풍이 모두 물든 상태여도 day = 1이 출력됐기 때문에 실패한 것이었다.

그래서 단풍이 물들었는지 검사하는 부분을 제일 위로, 그 다음에 day += 1을 구문을 배치하여 해결했다.