[level 2] [PCCP 기출문제] 2번 / 석유 시추 - 250136

문제 링크

성능 요약

메모리: 12.2 MB, 시간: 249.33 ms

구분

코딩테스트 연습 > PCCP 기출문제

채점결과

정확성: 60.0
효율성: 40.0
합계: 100.0 / 100.0

제출 일자

2025년 01월 06일 19:01:05

문제 설명

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

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

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

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

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

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

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.

정확성 테스트 케이스 제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 100

효율성 테스트 케이스 제한사항

• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

| [[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]] | 16 |

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

6번 열에 시추관을 설치하면 크기가 2, 1, 1, 12인 덩어리의 석유를 얻어 뽑을 수 있는 석유량이 16으로 가장 많습니다. 따라서 16을 return 해야 합니다.

제한시간 안내

• 정확성 테스트 : 10초
• 효율성 테스트 : 언어별로 작성된 정답 코드의 실행 시간의 적정 배수

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

💡 Solutions

📄 ［PCCP 기출문제］ 2번 ／ 석유 시추.py

from collections import deque

d = ((0,1), (0,-1), (1,0), (-1,0))

def bfs(sr, sc, land):
    global N, M
    que = deque()
    que.append((sr,sc))
    
    land[sr][sc] = 0
    count = 1
    
    oil_range = [sc, sc]
    
    
    while que:
        r, c = que.popleft()
        
        for dr, dc in d:
            nr = r + dr
            nc = c + dc
             
            if nr < 0 or nc < 0 or nr >= N or nc >= M: continue
            if not land[nr][nc] : continue
            
            land[nr][nc] = 0
            count += 1
            oil_range[1] = max(nc, oil_range[1])
            
            que.append((nr, nc))

        
    return oil_range, count

N = None
M = None

def solution(land):
    global N, M
    answer = 0
     # 이차원배열인데
    N = len(land) # 행의길이 
    M = len(land[0]) #열의 길이
    
    # for row in land:
    #     print(*row)
    
    
    
    
    
    oils = list()
    for m in range(M):
        for n in range(N):
            if not land[n][m] : continue
            count = bfs(n, m, land)
            oils.append(count)
            
    dig = [0 for _ in range(M)]
    for oil, count in oils:
        sc, ec = oil
        
        for i in range(sc, ec+1):
            dig[i] += count

    return max(dig)