[프로그래머스] 석유 시추 (Lv 2)

https://school.programmers.co.kr/learn/courses/30/lessons/250136

프로그래머스

 

bfs 극복중이다.

이번 문제의 핵심은, 연결된 부분의 넓이를 구하는 방법이다.

"새로 만나는 좌표"의 개수를 세 주면 되는 방식이다.

따라서, 시작점도 not_visited를 항상 체크해줘야 한다. 잊지 말자. 

아, 그리고 연결성을 활용하여 석유 시추하는 부분의 col 값의 최소/최대만 가져와도 나머지는 모두 연결성이 보장되어 있어 그 부분의 석유 값을 추가해주는 방식으로 구현하였다.

 

from collections import deque
mv_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
                
def solution(land):
    n, m = len(land), len(land[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    oil_list = [0] * m
    
    def bfs(land, visited, row, col):
    # 여기서 뱉어 줘야 하는 애는 x, y 최소 길이 수와, 넓이이다.
        queue = deque()
        min_col = col
        max_col = col
        size = 1
        visited[row][col] = True
        queue.append((row, col))

        while queue:
            cur_x, cur_y = queue.popleft()

            for mv in mv_list:
                nx = cur_x + mv[0]
                ny = cur_y + mv[1]
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    pass
                elif visited[nx][ny]:
                    pass
                elif land[nx][ny] == 0:
                    pass
                else:
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
                    size += 1
                    if ny < min_col : min_col = ny
                    if ny > max_col : max_col = ny
                    
        return [size, min_col, max_col]

    for row in range(len(land)):
        for col in range(len(land[0])):
            if land[row][col] == 1 and visited[row][col] == False:
                oil_size, min_col, max_col = bfs(land, visited, row, col)
                for k in range(min_col, max_col+1):
                    oil_list[k] += oil_size
    
    return max(oil_list)