문제
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일이 지나면 정원의 모든 꽃이 핍니다.
풀이
from queue import Queue
def solution(n, garden):
answer = 0
dx = [-1, 1, 0, 0] #동, 서
dy = [0, 0, -1, 1] # 북, 남
q = Queue()
for i in range(n):
for j in range(n):
if garden[i][j]==1:
q.put((i, j, 0)) #첫날 1있으면 좌표와 일수(0)넣기
while not q.empty():
x, y, day = q.get()
for i in range(4):
nx = x+dx[i] #다음 스텝
ny = y+dy[i]
nday = day+1 #다음날로 넘기기
if (nx >=0 and nx <n and ny >=0 and ny<n) and (garden[nx][ny]==0):
garden[nx][ny]=1 #꽃피우기
q.put((nx, ny, nday)) #꽃 위치와 날짜 삽입
answer = nday #하루 넘긴 날이 정답(여기서 꽃이 다 펴버리면 그다음날에 방문을 못하므로)
return answer첫 시도때 이중반복문 쓰고 난리났는데 알고보니 큐로 하는것이다
-
첫날에 리스트 순회하면서 1인곳 찾아냄
1-1. 큐에 좌표랑 날짜(0) 넣음 -
큐 순회
2-1. 1인곳 좌표랑 날짜 얻어내고 큐에서 삭제
2-2. dx, dy로 다음 좌표 정하고 날짜도 다음날로 넘김
2-3. 다음 방문한 곳이 인덱스에러를 일으키지 않는지, 그리고 꽃이 펴있지 않은지 검사
* 2-3-1. 검사완료 시 꽃 피우기
꽃 핀 곳 좌표와 날짜 큐에 넣기
nday가 곧 정답
Queue써가지고 좌표와 날짜를 put한다음 하나씩 빼서 다음날 좌표랑 일수 계산하고, 유효성검사(올바른 좌표와 꽃 폈는지)하는 걸 생각해내지 못했음
생각해보니까 이코테 시뮬레이션이랑 비슷함...배워놓고 까먹기^^
참고
