[프로그래머스] Cos Pro 1급 모의고사, 꽃 피는 봄이 언제 오나요

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

1. 문제
2. 풀이

---

문제

문제 설명

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

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

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

현재 정원의 상태를 담은 2차원 리스트 garden이 주어졌을 때, 모든 꽃이 피는데 며칠이 걸리는지 return 하도록 solution 함수를 작성해주세요.

 

매개변수 설명

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

• 정원의 한 변의 길이는 2 이상 100 이하입니다.
• 정원 상태를 담은 2차원 리스트 garden의 원소는 0 또는 1 입니다.
• 이미 핀 꽃은 1로 아직 피지 않은 꽃은 0으로 표현합니다.
• 정원에 최소 꽃 한 개는 피어 있습니다.

 

return 값 설명

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

 

예제

 

예제 설명

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

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

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

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

 

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

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

---

풀이

풀이 코드 및 해설

def solution(garden):
    answer = 0
      
    temp = [] # 좌표를 임시 저장할 리스트 생성
    dx = [1,0,-1,0] # 동남서북 좌표
    dy = [0,1,0,-1] # 리스트 생성
    
    while len(temp) < len(garden)**2: 
    	# garden의 크기가 꽉 찰 때까지 반복
        # temp는 1이 있는 위치만을 저장
        # len(garden)**2은 전체 밭의 크기
        # temp의 크기가 전체 밭의 크기가 똑같거나 더 큰 경우
        # 더 필 꽃이 없음
		
        temp.clear() # temp 리스트 초기화
        for i in range(len(garden)):
            for j in range(len(garden)): # 이중 for문으로 garden 순회
                if garden[i][j] == 1: # 만약 garden 순회 중 1을 만나면
                    temp.append([i,j]) # 임시 리스트에 좌표 값을 저장

        for i in temp: # 저장된 좌표 값을 i에 대입
            for j in range(4): # 동남서북 좌표만큼 반복
                x = i[0]+dx[j] # i[0]는 x 좌표 값, i[1]는 y 좌표 값
                y = i[1]+dy[j] # 4번 순회하며 동>남>서>북 좌표 값 유추
                if (x>=0 and x<len(garden)) and (y>=0 and y<len(garden)):
                # out of range를 고려하여 구간 설정
                    garden[x][y] = 1 # 4번 순회하며 동>남>서>북 좌표의 1 추가
        answer += 1 # 한번 순회하였으니 1일이 지났기 때문에 1일 추가
    return answer-1 # 마지막 순회한 날은 이미 다 꽃이 핀 상태이기 때문에 제외

---

해당 문제는 풀이에 어려움이 있어 아래의 블로그 글을 보고 이해하였습니다.

https://blog.naver.com/namucoding_pohang/222317624209