석유 시추

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)