[cos pro 1급] 꽃피는 봄이 언제오나요(BFS, 여러시작점)

꽃피우기

​

문제 설명

​

정사각형 크기 격자 모양 정원에 칸마다 핀 꽃 또는 피지 않은 꽃을 심었습니다.

이 정원의 꽃이 모두 피는 데 며칠이 걸리는지 알고 싶습니다.

핀 꽃은 하루가 지나면 앞, 뒤, 양옆 네 방향에 있는 꽃을 피웁니다.

​

현재 정원의 상태를 담은 2차원 리스트 garden이 주어졌을 때,

모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

​

매개변수 설명

​

현재 정원 상태를 담은 2차원 리스트 garden이 solution 함수의 매개변수로 주어집니다.

정원의 한 변의 길이는 2 이상 100 이하입니다.

정원 상태를 담은 2차원 리스트 garden의 원소는 0 또는 1 입니다.

이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.

정원에 최소 꽃 한 개는 피어 있습니다.

​

return 값 설명

​

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

​

예제

garden	return
[[0, 0, 0], [0, 1, 0], [0, 0, 0]]	2
[[1, 1], [1, 1]]	0

예제 설명

​

예제 #1

첫 날 정원은 아래와 같습니다.

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

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

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

​

예제 #2

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

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

 

문제풀이

from collections import deque

def BFS(n, position) :
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	visited = [[False] * (n) for _ in range(n)]
	distance = [[0] * (n) for _ in range(n)]
	dq = deque(position)					#1 좌표 큐에 넣기

	#다수의 시작 점 방문 처리
	for x, y in dq :
		visited[x][y] = True

	max_cnt = 0
	while dq :										#dq가 빌때까지
		now_x, now_y = dq.popleft()
		
		for d in range(4) :
			next_x = now_x + dx[d]
			next_y = now_y + dy[d]
	
			if 0 <= next_x < n and 0 <= next_y < n and visited[next_x][next_y] is False :
				dq.append((next_x, next_y))
				distance[next_x][next_y] = distance[now_x][now_y] + 1
				if max_cnt < distance[next_x][next_y] :
					max_cnt = distance[next_x][next_y]
				visited[next_x][next_y] = True
	return max_cnt
	
def solution(n, garden):
	answer = 0
	position = []
	for i in range(n) :
		for j in range(n) :
			if garden[i][j] == 1 :
				position.append((i, j))
	return BFS(n, position)