[Python/Programmers] [PCCP 기출문제] 2번 / 석유 시추

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

프로그래머스

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

오른쪽 그림처럼 7번 열에 시추관을 설치하면 크기가 7, 2인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 9로 가장 많습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

풀이

Code

from collections import deque

def solution(land):
    # 1. BFS 함수 정의
    def bfs(x, y) :
        cnt = 0
        min_y, max_y = y, y
        # 1-1. 큐에 현재 위치 삽입
        queue = deque()
        queue.append((x, y))
        # 1-2. 현재 위치 방문 처리
        visited[x][y] = True
        # 1-4.
        while queue :
            # 1-4-1. 큐에서 정보 반환
            x, y = queue.popleft()
            # 1-4-2. 열 범위 재설정
            min_y = min(min_y, y)
            max_y = max(max_y, y)
            # 1-4-3. 땅 개수 카운팅
            cnt += 1
            # 1-4-4.
            for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
                nx, ny = x + dir_x, y + dir_y
                # 예외 처리
                if nx < 0 or nx >= n or ny < 0 or ny >= m or not land[nx][ny]: continue
                # 해당 위치가 석유가 있는 땅이면서 방문하지 않은 경우
                if not visited[nx][ny] :
                    # 방문 처리
                    visited[nx][ny] = True
                    # 큐에 다음 위치 삽입
                    queue.append((nx, ny))
        # 1-5. 열 별 방문한 경우 출력 리스트에 값 추가
        for j in range(min_y, max_y+1) :
            answer[j] += cnt
    
    n, m = len(land), len(land[0])
    # 2. 출력 리스트 생성
    answer = [0 for _ in range(m)]
    # 3. 방문 여부 리스트 생성
    visited = [[False for _ in range(m)] for _ in range(n)]
    # 4. 
    for i in range(n) :
        for j in range(m) :
            # 4-1. 해당 위치가 석유가 있는 땅이면서 방문하지 않은 경우 BFS 실행
            if land[i][j] == 1 and not visited[i][j] : bfs(i, j)
    # 5. 최댓값 리턴
    return max(answer)