코딩 테스트(Python) [PCCP 기출문제] 2번 / 석유 시추

문제 설명

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

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

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

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

시추관의 위치 획득한 덩어리 총 석유량

1	[8]	8
2	[8]	8
3	[8]	8
4	[7]	7
5	[7]	7
6	[7]	7
7	[7, 2]	9
8	[2]	2

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

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

 

from collections import deque

def solution(land):
    # 초기화
    answer = 0
    n = len(land)  # 세로 크기
    m = len(land[0])  # 가로 크기
    visited = [[0 for i in range(m)] for i in range(n)]  # 방문 여부를 저장하는 2D 리스트
    result = [0 for i in range(m)]  # 각 열에서의 최대 값을 저장하는 리스트

    # BFS 함수 정의
    def bfs(a, b):
        # 이동 방향: 상하좌우
        dx = [0, 0, -1, 1]
        dy = [-1, 1, 0, 0]
        count = 0  # 현재 연결된 영역의 크기를 저장
        q = deque()  # BFS 탐색용 큐
        q.append((a, b))  # 시작점 추가
        min_y, max_y = b, b  # 현재 연결된 영역의 열 범위 초기화
        visited[a][b] = 1  # 시작점 방문 표시

        # BFS 탐색
        while q:
            count += 1  # 영역 크기 증가
            x, y = q.popleft()  # 현재 노드
            min_y = min(min_y, y)  # 연결된 영역의 최소 열 업데이트
            max_y = max(max_y, y)  # 연결된 영역의 최대 열 업데이트

            # 상하좌우로 이동
            for i in range(4):
                nx = x + dx[i]  # 다음 행
                ny = y + dy[i]  # 다음 열

                # 범위를 벗어나면 무시
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    continue

                # 방문하지 않았고, 연결된 영역이라면
                if visited[nx][ny] == 0 and land[nx][ny] == 1:
                    visited[nx][ny] = 1  # 방문 표시
                    q.append((nx, ny))  # 큐에 추가

        # 연결된 영역의 모든 열에 해당 영역의 크기 추가
        for i in range(min_y, max_y + 1):
            result[i] += count

    # 모든 위치를 탐색
    for i in range(n):
        for j in range(m):
            # 아직 방문하지 않았고, 연결된 영역이라면 BFS 수행
            if visited[i][j] == 0 and land[i][j] == 1:
                bfs(i, j)

    # 결과에서 가장 큰 값을 정답으로 설정
    answer = max(result)
    return answer