[Programmers] 석유 시추

문제

요약
석유관을 수직으로 꽂을 때, 어느 곳에서 꽂는 것이 가장 많은 양의 석유를 얻을 수 있는 지 구하시오.
 
원본

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

프로그래머스

---

풀이

1번 열에 석유관을 꽂았을 때, 이어져 있는 2번 열까지 이어지는 부분이 있다면,
2번 열에 석유관을 꽂아도 1번 열에서 확인했던 곳과 같은 곳을 다시 탐색하게 된다.
이점을 고려해서, 이미 석유 양을 확인한 곳은 처음 확인했던 자리에 석유 양을 저장 시켜 더할 수 있도록 했다.
 
좀 복잡하게 들릴 수 있지만 visited 배열을 출력해보면 쉽게 이해할 수 있다.

 

오른쪽 그림의 2번 열에서 시추관을 꽂았을 때, 왼쪽 출력처럼 처음 닿게 되는 위치가 (2, 0) 위치를 가리키기 때문에

visited[2][0]인 8을 더하게 된다. Set인 q에 (2,0)을 더해줘서 아래로 시추관이 내려가서 같은 양을 더하지 않도록 한다.

 

코드

from collections import deque
def solution(land):
    answer = 0
    
    n, m = len(land), len(land[0])
    stack = deque([])
    d = [(-1,0), (1,0), (0,-1), (0,1)]
    visited = [[0] * m for _ in range(n)]
    
    for j in range(m):
        cnt = 0
        q = set()
        for i in range(n):
        	# 채굴양에 더해지진 않았지만, 이전 열에서 석유양이 확인된 자리라면
            if visited[i][j] not in q and isinstance(visited[i][j], tuple):
                tx, ty = visited[i][j]
                # 채굴양에 더해줌
                cnt += visited[tx][ty]
                # 더했다는 것 표시
                q.add((tx, ty))
            
            # 처음 확인한 자리라면
            elif visited[i][j] == 0 and land[i][j] == 1:
                stack.append((i, j))
                
                while stack:
                    x, y = stack.popleft()
                    # 해당 자리에 석유양을 더해줌.
                    visited[i][j] += 1
                    
                    # 이어지는 구간 탐색
                    for dx, dy in d:
                        nx, ny = x+dx, y+dy
                        if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0 and land[nx][ny] == 1:
                            visited[nx][ny] = (i, j)
                            stack.append((nx, ny))
                # 열에서 채굴할 수 있는 양에 더해줌
                cnt += visited[i][j]
                # 이미 더해진 양이라는 것 표시
                q.add((i, j))
        
        answer = max(cnt, answer)
        
    return answer

 

정확성 테스트랑 효율성 테스트 속도랑 메모리는 아래와 같다.