[프로그래머스/파이썬] 석유 시추

내 풀이

from collections import deque


def solution(land):
    answer = 0
    m, n = len(land[0]), len(land)
    visited = [[0]*m for _ in range(n)]
    directions = [(0,1), (0,-1), (1,0), (-1,0)]
    answer_list = [0] * m # x 위치에 시추했을 때 얻을 수 있는 석유의 양을 바로바로 추가해줌
    
    def bfs(x, y):
        queue = [(x,y)]
        visited[y][x] = 1
        visited_x = {x} # 방문한 x를 저장해 해당 x에 count만큼 더해줌
        count = 1
        
        while queue:
            x,y = queue.pop(0)
            for direction in directions: # 상하좌우 확인
                next_x, next_y = x+direction[0], y+direction[1]
                
                if 0 <= next_x < m and 0 <= next_y < n: # 넘어가지 않고
                    if not visited[next_y][next_x] and land[next_y][next_x] == 1: # 방문하지 않고 석유가 있다면
                        visited[next_y][next_x] = 1
                        count += 1
                        queue.append((next_x, next_y))
                        visited_x.add(next_x)
		
        # 방문한 x에 count를 더해줌
        for vx in visited_x:
            answer_list[vx] += count
    
    # 전체를 하나씩 돌면서
    for i in range(n):
        for j in range(m):
        	# 석유가 있는지 체크하지 않았고 석유가 있다면 bfs 실행
            if not visited[i][j] and land[i][j] == 1:
                bfs(j, i)

    return max(answer_list) # 가장 큰 값 리턴

 

메모

머리가 안 돌 때는 쉬게 해주자.