[Python] 프로그래머스 석유 시추, 백준 16235 나무 재테크

1. 문제 - 프로그래머스 석유 시추(PCCP 기출문제)

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

 

💡알고리즘 - DFS/BFS

- 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리 ==> 그래프탐색을 통한 영역 짓기

 

✅ 풀이

import sys
sys.setrecursionlimit(10**6)    # 재귀 깊이를 늘려줘야 런타임 에러가 안뜸

def solution(land):
    answer = 0
    n = len(land)   # n: 세로길이 - x
    m = len(land[0])  # m: 가로길이 - y
    visited = [[False] * m for _ in range(n)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    num = 0   # 덩어리를 구분짓기 위한 숫자
    land_num = [[0] * m for _ in range(n)]
    
    def dfs(x, y):
        visited[x][y] = True
        temp.append((x, y))
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<n and 0<=ny<m and land[nx][ny] == 1 and not visited[nx][ny]:
                dfs(nx, ny)
                
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                num += 1
                temp = []
                dfs(i, j)
                size = len(temp)    # 석유 덩어리의 크기
                for x, y in temp:   # 같은 석유끼리 번호와 크기를 배정해 영역을 지어준다.
                    land[x][y] = size
                    land_num[x][y] = num
                                        
    for i in range(m):
        oil_set = set()
        for j in range(n):
            if land[j][i] != 0:  # 같은 사이즈라도 다른 영역일 수 있어 번호와 함께 set에 추가해줌
                oil_set.add((land_num[j][i], land[j][i]))
                
        _sum = 0
        for num, amount in oil_set:
            _sum += amount
                
        answer = max(answer, _sum)    # 시추할 수 있는 석유의 합 최대값 갱신하기
    
    return answer

 

- 석유가 있지만 아직 방문하지 않은 영역을 만나면, DFS를 통해 방문처리하고 좌표를 저장한다.

- 상하좌우에 인접하는 좌표의 갯수 합이 곧 석유 덩어리 영역의 크기(size)이다. 기존 land 에는 좌표에 size를 저장하고, land_num에는 같은 석유 크기일지라도 다른 영역임을 구분하기 위한 영역 숫자(num)을 대입한다.

- 그리고 세로의 크기(m)마다 반복하며 oil_set 집합에 영역 숫자 num과 영역의 크기 (land[i][j])를 함께 튜플로 저장한다.

==> 집합에 저장하는 이유는 land에 접근할 때 같은 석유 영역임에도 여러 번 들어갈 수 있으므로 중복 제거하기 위함

- 이때 !! 주의할점은 나는 DFS로 풀이했는데, 재귀 깊이를 반드시 따져봐야한다.

기본 Python의 재귀 깊이는 10,000 이지만 n과 m이 각각 최대 500이라면 최악의 경우 재귀는 250,000 깊이를 가지게 된다.

이 경우 런타임 에러가 발생하므로, import sys / sys.setrecursionlimit(10**6) 등으로 입력값 이상으로 재귀 깊이를 지정한다.

 

✅ 다른 풀이

import sys
sys.setrecursionlimit(10**6)    # 재귀 깊이를 늘려줘야 런타임 에러가 안뜸

def solution(land):
    answer = 0
    n = len(land)   # n: 세로길이 - x
    m = len(land[0])  # m: 가로길이 - y
    visited = [[False] * m for _ in range(n)]
    cols = [0] * m
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def dfs(x, y):
        nonlocal size
        
        visited[x][y] = True
        size += 1
        temp.add(y)
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<n and 0<=ny<m and land[nx][ny] == 1 and not visited[nx][ny]:
                dfs(nx, ny)
                
    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                temp = set()
                size = 0
                dfs(i, j)
                for y in temp:
                    cols[y] += size                
    
    return max(cols)

 

- 좌표를 일일이 저장하는게 아니라, y좌표만 저장하되 중복 제거를 위해 set를 사용한 부분이 다르다.

- 각 y좌표마다 얻을 수 있는 석유들을 cols라는 배열을 통해 저장하면, 해당 배열의 최대값이 시추할 수 있는 석유의 최대값이다. 

 

2. 문제 - 백준 16235 나무 재테크

https://www.acmicpc.net/problem/16235

 

💡알고리즘 - 시뮬레이션/구현

 

❌ 시간초과 풀이

n, m, k = map(int, input().split())
# nxn 크기의 땅
board = [[5] * n for _ in range(n)]
A = []  # 겨울에 추가되는 양분의 양
trees = [[[] for _ in range(n)] for _ in range(n)]  # 각 칸마다의 나무 나이, 여러 개의 나무가 있을 수도 있다
for _ in range(n):
  A.append(list(map(int, input().split())))
for _ in range(m):
  x, y, z = map(int, input().split())
  trees[x-1][y-1].append((z, False))

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

for _ in range(k):
  # 봄
  for i in range(n):
    for j in range(n):
      if trees[i][j]:
        trees[i][j].sort(key=lambda x: x[0])
        temp = []
        for age, isDead in trees[i][j]:    # 나이가 어린 나무부터 양분을 먹기 위해 정렬
          if not isDead:
            if board[i][j] < age: # 양분 부족
              temp.append((age, True))
            else:
              board[i][j] -= age  # 나이만큼의 양분을 먹고, 나이 1 증가
              temp.append((age+1, False))

        trees[i][j] = temp
  
  # 여름
  for i in range(n):
    for j in range(n):
      if trees[i][j]:
        for age, isDead in trees[i][j]:
          if isDead:   # 죽은 나무인 경우에만 양분 추가
            board[i][j] += age // 2
  
  # 가을
  for x in range(n):
    for y in range(n):
      if trees[x][y]:
        for age, isDead in trees[x][y]:
          if age % 5 == 0 and not isDead:
            for l in range(8):
              nx = x + dx[l]
              ny = y + dy[l]

              if 0<=nx<n and 0<=ny<n:
                trees[nx][ny].append((1, False))
  
  # 겨울
  for i in range(n):
    for j in range(n):
      board[i][j] += A[i][j]

answer = 0

for i in range(n):
  for j in range(n):
    if trees[i][j]:
      for _, isDead in trees[i][j]:
        if not isDead:
          answer += 1

print(answer)

 

- 42% 정도에서 시간초과가 걸린다.

- 원인은 봄에 "나이가 어린 나무부터 양분을 먹는다"를 위해 매년 매 칸에 있는 나무를 매번 정렬하는 부분에서 시간초과가 발생하는 것으로 추측했다.

 

✅ 풀이

from collections import deque

n, m, k = map(int, input().split())
# nxn 크기의 땅
board = [[5] * n for _ in range(n)]
A = []  # 겨울에 추가되는 양분의 양
trees = [[deque() for _ in range(n)] for _ in range(n)]  # 각 칸마다의 나무 나이, 여러 개의 나무가 있을 수도 있다
for _ in range(n):
  A.append(list(map(int, input().split())))
for _ in range(m):
  x, y, z = map(int, input().split())
  trees[x-1][y-1].append((z, False))
for i in range(n):
  for j in range(n):
    if trees[i][j]:
      trees[i][j] = deque(sorted(trees[i][j]))

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

for _ in range(k):
  # 봄
  for i in range(n):
    for j in range(n):
      if trees[i][j]:
        temp = deque([])
        for age, isDead in trees[i][j]:
          if not isDead:
            if board[i][j] < age: # 양분 부족
              temp.append((age, True))
            else:
              board[i][j] -= age  # 나이만큼의 양분을 먹고, 나이 1 증가
              temp.append((age+1, False))

        trees[i][j] = temp
  
  # 여름
  for i in range(n):
    for j in range(n):
      if trees[i][j]:
        for age, isDead in trees[i][j]:
          if isDead:   # 죽은 나무인 경우에만 양분 추가
            board[i][j] += age // 2
  
  # 가을
  for x in range(n):
    for y in range(n):
      if trees[x][y]:
        for age, isDead in trees[x][y]:
          if age % 5 == 0 and not isDead:
            for l in range(8):
              nx = x + dx[l]
              ny = y + dy[l]

              if 0<=nx<n and 0<=ny<n:
                trees[nx][ny].appendleft((1, False))   # 그 다음해 봄에 나이가 어린 나무부터 양분을 먹게 하기 위해 앞에 추가함
  
  # 겨울
  for i in range(n):
    for j in range(n):
      board[i][j] += A[i][j]

answer = 0

for i in range(n):
  for j in range(n):
    if trees[i][j]:
      for _, isDead in trees[i][j]:
        if not isDead:
          answer += 1

print(answer)

- 처음 입력받은 나무 배열을 정렬하되, 이후에 나이가1인 나무를 추가할 때 뒤가 아닌 앞으로 추가하게 하여 그 다음해의 봄에 정렬하지 않아도 나이 어린 나무부터 양분을 먹을 수 있도록 한다.

- 나무를 저장할 trees 배열을 각 칸이 deque()인 2차원 배열로 변경했다. (배열의 insert(0) 보다 큐의 appendleft가 시간복잡도가 더 빠르기 때문)

 

새롭게 알게된 점

- 기본 python의 재귀 깊이는 10,000이다.

- 문제의 최대 재귀 깊이는 입력값(n)의 최대 크기를 가지고 판단한다. 이를 넘을 경우 import sys / sys.setrecursionlimit(10**6) 으로 적절하게 재귀 깊이를 늘려주어야한다.

- ⭐️ ⭐️ ⭐️ 반복문을 돌고 있는 리스트를 반복문 안에서 변경하지 말자