COS Pro 1급 기출문제 - 꽃피우기

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

할 때마다 모르겠는 DFS BFS

BFS 방식으로 풀어보려고 했다. 반복문 범벅이라 효율적인진 잘 모르겠지만 ㅠ

 

https://school.programmers.co.kr/learn/courses/11133/lessons/71165

프로그래머스

---

구현 방식

1. 먼저 입력으로 주어진 밭에서 1의 위치를 찾아 one 리스트에 저장

2. 모든 위치의 꽃을 피울 때까지 (count로 확인, BFS 알고리즘에서 자주 사용하는 visited를 안 쓰고 모든 위치를 갔는 지 확인하려고 사용함) 네 방향으로 새로 꽃을 피우고 위치 저장

 

생각해야 할 부분

-  3번으로 표시한 부분 코드를 처음에 안 넣었었음. garden의 값을 실제로 바꾸지 않아도 횟수는 카운팅 되니까 괜찮을 줄 알았는데 그러면 중복 파악이 안 되어 무한루프로 들어감.

- 처음에 one, two 리스트를 하나의 변수에서 넣고 빼고 했더니 같은 날 번식(?)해야하는 데 새로운 위치들이 쌓이면서 밀려버림. 그래서 (오늘 새로 번식한 위치 = two)로 따로 만들어서 하루가 지난 후에 one에 넣어줌.

 

 

def solution(garden):
    answer = 0
    direct=[[0,1],[-1,0],[0,-1],[1,0]] # 아래, 왼쪽, 위, 오른쪽
    length=len(garden)
    one=[]
    count=0
    # 1
    for i in range(length):
        for j in range(length):
            if garden[i][j] == 1:
                one.append([i,j])
                count+=1
	# 2
    while count!=length**2:
        two=[]
        while one:
            now=one.pop()
            for k in direct:
                flower=[now[0]+k[0], now[1]+k[1]]

                if (flower[0]>-1 and flower[0]<length) and (flower[1]>-1 and flower[1]<length):
                    # 3
                    if garden[flower[0]][flower[1]] != 1:
                        garden[flower[0]][flower[1]] = 1    
                        two.append([flower[0],flower[1]])
                        count+=1
        one=two
        answer+=1 
    return answer
    
# 아래는 테스트케이스 출력을 해보기 위한 코드입니다.
garden1 = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0,0,0,0,0], [0,0,0,0,0]]
ret1 = solution(garden1)