문제

https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3

코드

from collections import deque
def solution(land):
    N = len(land)
    M = len(land[0])
    
    visited = [[False for _ in range(M)] for _ in range(N)]
    result = [0 for _ in range(M)]
    
    def bfs(x,y):
        Q = deque([(x,y)])
        visited[x][y] = True
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]
        
        y_list = set()
        count = 1
        while Q:
            x,y = Q.popleft()
            y_list.add(y)
            
            for i in range(4):
                nx,ny = x + dx[i], y + dy[i]
                
                if 0<=nx<N and 0<=ny<M and visited[nx][ny] == False and land[nx][ny]==1:
                    count += 1
                    Q.append((nx,ny))
                    visited[nx][ny] = True
                    
                    
        for c in y_list:
            result[c] += count
            
    for i in range(N):
        for j in range(M):
            if visited[i][j] == False and land[i][j] ==1:
                bfs(i,j)
    
    
    return max(result)

풀이

• BFS를 사용하는 것이 효율성 측면에서 좋음.
• 석유가 있는 곳의 열을 y_list에 저장.
• 각 열에 대한 result를 만들어놓고, 열을 기준으로 count를 더해놓음.