프로그래머스 lv2. 석유 시추

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

프로그래머스

dfs로 풀었다.

다른 사람들의 풀이를 보니 대부분 bfs를 사용하였다.

 

기본 발상은 이러하다.

 

1. dfs 등의 탐색 알고리즘을 활용해서 각 석유 덩어리들의 크기를 먼저 구한다.

2. 해당 석유 덩어리가 걸치고 있는 수직 라인의 좌표를 기록한다.

3. 해당 좌표에서 시추할 수 있는 석유의 총량을 합한다.

---

import sys
sys.setrecursionlimit(1000000)

vertical = set()

# 석유 덩어리의 크기를 구하기
def dfs(x, y, land):
    global cnt
    if (x > max_x - 1 or x < 0) or (y > max_y - 1 or y < 0):
        return False
    if not land[x][y]:
        return False
    vertical.add(y)
    land[x][y] = 0
    cnt += 1
    dfs(x - 1, y, land)
    dfs(x, y + 1, land)
    dfs(x + 1, y, land)
    dfs(x, y - 1, land)
    return True

def solution(land):
    # 석유 덩어리의 크기와 그 덩어리가 걸치는 수직 좌표를 적을 리스트
    oil_vertical = []
    
    # 각 수직선상에서 시추할 수 있는 유량을 적을 딕셔너리 
    res = {}
    
    global vertical
    global max_x
    global max_y
    global cnt
    max_x = len(land)
    max_y = len(land[0])
    cnt = 0
    
    # 석유 덩어리 탐색
    for i in range(max_x):
        for j in range(max_y):
            if land[i][j]:
                cnt = 0
                dfs(i, j, land)
                oil_vertical.append((cnt, list(vertical)))
                vertical = set()
    
    """
    송유관을 수직으로 뚫을 때 지나갈 수 있는 모든 석유의 양을 구하기 위한 반복문
    """
    for oil, vertical in oil_vertical:
        for point in vertical:
            # 해당 좌표가 딕셔너리에 없으면 초기화
            if point not in res:
                res[point] = oil
            # 이미 걸쳐지는 석유 덩어리의 수직 좌표에 새로운 석유량을 추가
            else:
                res[point] += oil
    
    return max(res.values())

---

처음 제출할 때는 맨 위의,

import sys
sys.setrecursionlimit(1000000)

 

를 빼고 제출했다.

 

그랬더니 정확성 테스트는 퍼펙트한데 계속 효율성 테스트에서 런타임 에러가 발생했다.

거기서 포기하고 bfs로 다시 구현하기가 귀찮았는데, 그 때 생각났던 사례가 아래의 사례이다.

https://mhd329.tistory.com/17

백준 1012 : 유기농 배추 (파이썬)

여기에서 dfs를 이용해서 풀 때 시스템 재귀제한에 막혀서 계속 에러가 발생한 적이 있다.

예전에 저걸 몰랐을 때는 분명 맞을텐데 왜 안되지 하고 계속 고민했던 적이 있는데,

이번에도 런타임 에러인걸 보니 그런 경우인가 싶어서 재귀 제한을 해제하였고, 문제가 해결되었다.

---

다른 사람들의 경우 bfs로 푸는 과정은 별 차이가 없는데, 마지막에 수직 좌표에 해당하는 부분을 처리하는 과정에서 나와 약간의 차이를 보였다.

 

나는 딕셔너리를 통해서 총량을 구했는데 다른 사람들은 아래와 같이 풀었다.

 

1. 내부 값들을 0으로 채운 열 길이 만큼의 1차원 리스트를 만든다.

...
# W는 열의 길이
oil_list = [0] * W
...

2. 탐색을 하며 각 수직 좌표를 set에 담아서 중복되지 않게 한다.

...
width = set()
...
width.add(y)
...

3. set에 담겨있던 좌표들을 하나씩 꺼내면서 좌표 리스트에서 인덱싱하여 해당 위치의 유량을 누적시킨다.

...
for y in width:
    oil_list[y] += amount
...

4. 누적된 값들 중 max값을 출력한다.

...
return max(oil_list)

 

이 방법이 훨씬 더 직관적이고 쉬운 것 같은데 왜 떠올리지 못했지?

아마도 각 좌표에 유량을 대응시킨다는 발상으로부터 key, value 식의 구조를 떠올려서 그런 것 같다.