[코테 풀이] 프로그래머스 - Lv.2 [PCCP 기출문제] 2번 / 석유 시추 (Python)

문제

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 함수를 완성해 주세요.

 

제한사항

• 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
문제의 예시와 같습니다.

입출력 예 #2

 

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

 

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

 

제한시간 안내

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

---

접근 방법

시추할 때 연결된 모든 석유들을 찾아야 한다. 탐색 문제이기 때문에 BFS로 접근했다.

하지만 해당 column의 시추를 마치고 다음 column을 시추할 때, 석유 그룹을 다시 탐색하면 시간 초과가 발생한다.

이 문제를 적절히 해결해야 할 것이다.

---

코드

시간 초과 코드 1

시추할 때마다 석유 덩어리를 재탐색해서 효율성 테스트 전부 실패

from collections import deque
import copy

def bfs(row, col, land):
    n, m = len(land), len(land[0])
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    
    q = deque([(row, col)])
    oil = 0  
    while len(q) != 0:
        y, x = q.popleft()
        if land[y][x] == 1:
            oil += 1
            land[y][x] = 0
            for i in range(4):        
                ny = y + dy[i]
                nx = x + dx[i]
                if ny >= 0 and ny < n and nx >= 0 and nx < m:
                    if land[ny][nx] == 1:
                        q.append((ny, nx))
    
    return land, oil        

def solution(land):
    n, m = len(land), len(land[0])
    total_oil = [0] * m
    
    for col in range(m):
        tmp_land = copy.deepcopy(land)
        for row in range(n):
            tmp_land, oil = bfs(row, col, tmp_land)
            total_oil[col] += oil
    
    return max(total_oil)

 

시간 초과 코드 2

석유가 있을 때만 탐색을 수행하고, 탐색했던 석유 덩어리는 다음 시추에서 다시 탐색하지 않도록 수정했으나

효율성 테스트 2, 3번에서 시간 초과

from collections import deque

def bfs(row, col, land):
    n, m = len(land), len(land[0])
    visited_col = [False] * m
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    
    q = deque([(row, col)])
    oil = 0
    while len(q) != 0:
        y, x = q.popleft()
        if land[y][x] == 1:
            visited_col[x] = True
            oil += 1
            land[y][x] = 0
            for i in range(4):        
                ny = y + dy[i]
                nx = x + dx[i]
                if ny >= 0 and ny < n and nx >= 0 and nx < m:
                    if land[ny][nx] == 1:
                        q.append((ny, nx))
    
    return land, oil, visited_col

def solution(land):
    n, m = len(land), len(land[0])   
    total_oil = [0] * m
    for col in range(m):
        for row in range(n):
            if land[row][col] == 1:
                land, oil, visited_col = bfs(row, col, land)
                for i in range(m):
                    if visited_col[i] == True:
                        total_oil[i] += oil
    
    return max(total_oil)

 

정답 코드

시추할 때 방문했던 열 visited_col이 boolean값을 가지고, '길이가 전체 열의 개수'로 한 것이 문제였다. 최대 500번의 반복이 추가된다.

방문한 열만 담고 있도록 visited_col을 집합(set)으로 만들고 중복이 제거된 index 값을 담고 있도록 수정했다.

from collections import deque

def bfs(row, col, land):
    n, m = len(land), len(land[0])
    visited_col = set()
    dy = [0, 0, 1, -1]
    dx = [1, -1, 0, 0]
    
    oil = 0
    q = deque([(row, col)])
    while len(q) != 0:
        y, x = q.popleft()
        if land[y][x] == 1:
            visited_col.add(x)
            oil += 1
            land[y][x] = 0
            for i in range(4):        
                ny, nx = y + dy[i], x + dx[i]
                if 0 <= ny < n and 0 <= nx < m:
                    if land[ny][nx] == 1:
                        q.append((ny, nx))
    
    return land, oil, visited_col

def solution(land):
    n, m = len(land), len(land[0])
    total_oil = [0] * m
    for col in range(m):
        for row in range(n):
            if land[row][col] == 1:
                land, oil, visited_col = bfs(row, col, land)
                for i in visited_col:
                    total_oil[i] += oil                    
                    
    return max(total_oil)