[BFS/DFS] 프로그래머스 COS Pro 1급 꽃피우기 (Python 파이썬)

💡문제 링크

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

 

💡문제 분석 요약

꽃이 피어있으면 1이고, 다음 번에 상하좌우로 1이 된다(상하좌우로 꽃이 핀다)

정원에 있는 모든 꽃이 다 피기까지 걸리는 날짜를 구하는 문제

 

💡알고리즘 설계

일단 쭉쭉 밖으로 뻗어나가는 구조이니까 BFS임을 파악한다.

근데 그 이후로 어떻게 해야할지 몰라서 다른 풀이를 참고했다..

 

💡코드

from collections import deque
def solution(garden):
    n = len(garden)
    answer = 0
    dx = [-1, 1, 0, 0] #동, 서
    dy = [0, 0, -1, 1] # 북, 남

    # 첫 날, 1인 곳의 위치를 큐에 넣기
    q = deque()
    for i in range(n):
        for j in range(n):
            if garden[i][j]==1: 
                q.append((i, j, 0)) #첫날 1있으면 좌표와 일수(0)넣기

    # 큐가 빌 때까지 하나씩 꺼내기
    while q:
        x, y, day = q.popleft() 

        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.append((nx, ny, nday)) #꽃 위치와 날짜 삽입
                answer = nday #하루 넘긴 날이 정답(여기서 꽃이 다 펴버리면 그다음날에 방문을 못하므로)
    return answer

 

💡 오답 풀이

...

 

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

알듯말듯 모르겠어서 다른 풀이 참고함.

dx, dy 리스트 만들어서 탐색하는 bfs 코드는 그냥 외워버리자!