[프로그래머스] PCCP 기출 문제 2번 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/19344/lessons/242259
• 🔑 BFS
  • 석유가 있으면 현재 좌표를 가지고 BFS를 호출한다.
  • 석유가 있는 덩어리의 크기를 구한다. (cnt)
  • 덩어리의 열 위치를 저장한다. (lst)
  • 저장한 덩어리 열 위치에  덩어리의 크기를 누적 시킨다. (answer)
  • 누적 시킨 리스트의 최댓값이 답 ✨

 

 

from collections import deque

def solution(land):
    answer = [0] * len(land[0])
        
    mx, my = [0, 0, 1, -1], [1, -1, 0, 0]
    visit = [[0] * len(land[0]) for _ in range(len(land))]
    
    def bfs(x, y):
        q = deque([[x, y]])
        cnt = 1             # 석유 덩어리 크기
        lst = [y]           # 석유가 있는 열을 담는 리스트
        
        while q:
            now_x, now_y = q.popleft()
            
            for i in range(4):
                next_x, next_y = now_x + mx[i], now_y + my[i]
                
                if 0 <= next_x < len(land) and 0 <= next_y < len(land[0]) and land[next_x][next_y] == 1 and visit[next_x][next_y] == 0:
                    q.append([next_x, next_y])
                    visit[next_x][next_y] = 1
                    lst.append(next_y)                  # 덩어리 열 위치 저장
                    cnt += 1                            # 덩어리 크기 증가

        for col in set(lst):                            # 석유가 있는 열에 석유 덩어리 크기를 누적한다.
            answer[col] += cnt
    
    for i in range(len(land)):                          # 석유가 있는 덩어리 찾기
        for j in range(len(land[0])):
            if land[i][j] == 1 and visit[i][j] == 0:
                visit[i][j] = 1
                bfs(i, j)
    
    return max(answer)