[프로그래머스] 석유 시추

문제 이해하기

시추관을 세로로 뚫었을 때 최대 몇 개의 오일을 뽑을 수 있을까를 묻는 문제였다.

아래 그림과 같이 7번으로 뚫었을 때는 총 9개의 오일을 뽑을 수 있는 것을 볼 수 있다 

 

문제 해결 방법 설명하기

1. DFS알고리즘을 이용해 그룹을 나누기로 결정했다. 처음에는 최대 석유 개수를 기록하려고 했는데 아래 오른쪽 그림과 같은 상황에서는 원하는 답을 찾을 수 없기 때문에 그룹으로 나누었다.예를들면 6번 라인에서 굴착을 하면 [2, 1, 1, 12]만큼 오일을 얻을 수 있다는 것을 알기가 어려울 것 같았다.

 

2. 굴착을 했을 때 어떤 그룹들이 있는지를 저장했다. 아래 그림과 같은 경우에는 초록색 그룹이 3개나 발견됐는데 중복을 제거하는 코드가 필요하다.

 

3. 그 후 시추 1, 2, ~ 8까지 반복문을 돌면서 최대로 얻을 수 있는 오일 양을 계산하도록 했다. 

 

 

 

코드

import sys
sys.setrecursionlimit(1000000)

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def is_out_range(x, y, mx, my):
    if x < 0 or x >= mx or y < 0 or y >= my:
        return True
    return False

def dfs(x, y, lands, groupNum, hopCount):
    lands[x][y] = groupNum
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
    
        if is_out_range(nx, ny, len(lands), len(lands[0])):
            continue
        #미발견 지역
        if lands[nx][ny] == 1:
            lands[nx][ny] = groupNum
            hopCount = max(hopCount, dfs(nx, ny, lands, groupNum, hopCount + 1))
            
    return hopCount

"""_summary_
    오일이 있는 지점부터 시작해서 상하좌우로 이동하면서 같은 그룹으로 묶어준다.
    그룹에 속해 있는 오일의 개수를 구한 후 그룹별로 저장한다
    
    그 후 각 열에 속해있는 그룹을 모두 리스트에 저장한 후 set을 이용해 중복을 제거한다.
    그 후 그룹 별로 저장한 오일의 개수를 다 더해서 최대 값을 반환한다
"""
def solution(lands):
    ans = 0
    group = 2
    oil_count_by_group = {}
    
    for i in range(len(lands)):
        for j in range(len(lands[i])):
            if lands[i][j] == 1:
                maxHopCount = dfs(i, j, lands, group, 1)
                oil_count_by_group[group] = maxHopCount
                group += 1
    
    for j in range(len(lands[0])):
        cand_group = []
        for i in range(len(lands)):
            if lands[i][j] != 0:
                cand_group.append(lands[i][j])
                
        cand_group = set(cand_group)
        temp_ans = 0
        
        for temp in cand_group:
            temp_ans += oil_count_by_group[temp]
        
        ans = max(ans, temp_ans)
        
    return ans


if __name__ == "__main__":
    land = [[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]]    # print(len(land))
    
    print(solution(lands=land))

배운점 정리하기

처음에는 DFS 두 개로 해결했지만, 조금 더 생각해보니 그룹 별로 나누면 꼭 land에 최대 개수를 기록 할 필요가 없었다.