[COS PRO 1급 #6-1] 꽃피는 봄이 언제 오나요

문제설명

n x n 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다. 이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다. 핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다. 
정원 크기 n과 현재 정원의 상태를 담은 2차원 리스트 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

매개변수 설명

정원 크기 n과 현재 정원 상태를 담은 2차원 리스트 garden이 solution 함수의 매개변수로 주어집니다.
* 정원 크기 n은 1보다 크고 100 보다 작거나 같은 자연수입니다.
* 정원 상태를 담은 2차원 리스트 garden의 원소는 0 또는 1 입니다.
* 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
* 정원에 최소 꽃 한 개는 피어 있습니다.

return 값 설명

꽃이 모두 피는데 며칠이 걸리는지 return 합니다.

예시

| n | garden                         | return |
|---|-----------------------------------|--------|
| 3 | [[0, 0, 0], [0, 1, 0], [0, 0, 0]] | 2   |
| 2 | [[1, 1], [1, 1]]               | 0   |

예시 설명

예시 #1
첫 날 정원은 아래와 같습니다.

 

1일이 지난 정원의 상태는 아래와 같습니다.

 

2일이 지난 정원의 상태는 아래와 같습니다.

 

따라서, 2일이 지나면 정원의 모든 꽃이 핍니다.

예시 #2
첫 날 화단의 상태는 아래와 같습니다.

 

따라서, 0일이 지나면 정원의 모든 꽃이 핍니다.

문제 코드

def solution(n, garden):
    #여기에 코드를 작성해주세요.
    answer = 0
    return answer

풀이 1

def solution(n, garden):
	answer = 0

	while True:
		
		# garden에서 꽃이 핀 칸의 개수 구하기
		flower = 0
		for y in range(n):
			for x in range(n):
				if garden[y][x] == 1:
					flower += 1
		
		# garden에 전부 꽃이 폈으면 while문 탈출
		if flower == n*n:
			break
		
		# 꽃이 핀 칸의 상하좌우 칸은 1일 지나면 꽃이 핌
		garden_temp = garden
		for y in range(n):
			for x in range(n):
				if garden[y][x] == 1:
					if y+1 < n:
						garden_temp[y+1][x] = 1
					if y-1 >= 0:
						garden_temp[y-1][x] = 1
					if x+1 < n:
						garden_temp[y][x+1] = 1
					if x-1 >= 0:
						garden_temp[y][x-1] = 1

		garden = garden_temp
		answer += 1

	return answer

풀이 2

import queue

def solution(n, garden):
    answer = 0

    q = queue.Queue()
    dx = [ -1, 1, 0, 0 ]
    dy = [ 0, 0, -1, 1 ]

    for i in range(n) :
    	for j in range(n) :
    		if garden[i][j] == 1 :
    			q.put((i, j, 0))

    while q.empty() == False :
    	x, y, day = q.get()

    	for i in range(4) :
    		next_x = x + dx[i]
    		next_y = y + dy[i]
    		next_day = day + 1

    		if (0 <= next_x and next_x < n and 0 <= next_y and next_y < n) and (garden[next_x][next_y] == 0) :
    			garden[next_x][next_y] = 1
    			answer = next_day
    			q.put((next_x, next_y, next_day))

    return answer