문제 링크

풀이 과정

전체 코드

from collections import deque

def isin_boundary(row, col, row_len, col_len):
    row_cond = (row >= 0 and row < row_len)
    col_cond = (col >= 0 and col < col_len)
    return row_cond & col_cond

def solution(land):
    '''
    1. 각 열마다 몇 개의 석유를 획득할 수 있는지 기록해야 함.
        -> 열의 길이 만큼의 배열을 생성
    2. 매 BFS 수행 시마다,
        - 탐방 가능한 열을 기록
        - 시추 사능한 석유 갯수 집계
    3. BFS가 끝날 때마다, 해당 열마다 시추 가능한 석유 갯수 추가
    '''
    row_len, col_len = len(land), len(land[0])  # 행 길이, 열 길이
    answer = [0 for _ in range(col_len)]  
    visited_list = [[0 for _ in range(col_len)] for _ in range(row_len)]   # 방문 리스트
    delta = [(-1,0), (1,0), (0,-1), (0,1)]  # 변화량 (상,하,좌,우 방향)
    
    for row in range(row_len):
        for col in range(col_len):
            if (land[row][col] == 1) and (visited_list[row][col] == 0):
                queue = deque()
                queue.append((row, col))
                oil_num = 1  # 해당 구역에서 시추 가능한 석유 갯수
                visited_cols = [col]  # 탐방한 열 목록
                visited_list[row][col] = 1  # 방문 처리
                
                while queue:   # BFS 수행
                    y, x = queue.pop()
                    for dy, dx in delta:
                        new_y, new_x = y+dy, x+dx
                        if isin_boundary(new_y, new_x, row_len, col_len):
                            if visited_list[new_y][new_x] == 0 and land[new_y][new_x] == 1:
                                visited_list[new_y][new_x] = 1  # 방문 처리
                                oil_num += 1  # 석유 갯수 추가
                                queue.append((new_y, new_x))
                                if new_x not in visited_cols:
                                    visited_cols.append(new_x)
                                
                for visited_col in visited_cols:  # 방문한 열마다 석유 갯수 추가
                    answer[visited_col] += oil_num
                                
    return max(answer)