[백준 알고리즘] - 토마토 (7569번) with Python

📎 간략한 문제 정리

• 기존의 토마토 문제(https://jayb-log.tistory.com/126) 를 3차원으로 변경한 문제입니다. 익은 토마토 주변의 토마토는 익게 되는데, 모든 토마토가 익게 될 때까지 걸리는 시간을 측정하는 문제입니다.

📈 문제 분석

• BFS/DFS 문제로 조건에 맞춰 주변을 탐색합니다. 기존 토마토 문제와 다른 점은 3차원이기 때문에 dx, dy로 2방향만 보는 것이 아니라 위 아래도 관찰하는 dz도 관찰해야 하는 차이가 있습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 각 시점에 따라서 주변에 상황이 변해가는 것이므로 DFS보다 BFS가 적합합니다.

💻 풀이한 코드

from sys import stdin
from collections import deque
input = stdin.readline
m, n, h = map(int, input().split())
tomato = [[list(map(int, input().split())) for _ in range(n)] for _ in range(h)]
visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(h)]
days = 0
max_day = 0
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
def bfs():
    global max_day
    while visiting:
        x, y, z, day = visiting.popleft()
        for i in range(6):
            xx, yy, zz = x + dx[i], y + dy[i], z + dz[i]
            if 0 <= xx < m and 0 <= yy < n and 0 <= zz < h:
                if not visited[zz][yy][xx] and tomato[zz][yy][xx] == 0:
                    visited[zz][yy][xx] = True
                    tomato[zz][yy][xx] = 1
                    visiting.append((xx, yy, zz, day+1))
                    if day + 1 > max_day:
                        max_day = day + 1
def is_all_riped(tomato):
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if tomato[i][j][k] == 0:
                    return False
    return True
visiting = deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k] == 1:
                visiting.append((k, j, i, days))
bfs()
if is_all_riped(tomato):
    print(max_day)
else:
    print(-1)

📝 해결 과정에서 만난 문제, 고민들

• 전역 변수에 대한 문제:

  위의 코드는 기본적으로 main 함수로 작성되기 때문에 bfs 같은 메소드는 main 함수 안에서 정의된 함수입니다. 그래서 main에서 정의된 변수들은 같은 Scope인 bfs에서도 문제없이 작동할 것이라고 생각하여 전역처리하지 않았습니다. tomato나 visited 같은 리스트, deque 구조에서는 문제가 없었습니다. 하지만 max_day에서 문제가 발생했습니다. max_day에서만 문제가 발생한 것이 이상하여 검색해보니 다음과 같은 문제가 있었습니다.

  1. First - because in python we have mutable and immutable classes. Ints are immutable, that is when you write x+=1 you actually create another object (which is not true for certain ints due to optimisations CPython does). What actually happens is x = x + 1.
  2. Second - because python compiler checks every assignment made inside a scope and makes every variable assigned inside that scope local to it.
  3. So as you see when you try to increment x compiler has to access a variable that's local to that scope, but was never assigned a value before.

  해석하면 다음과 같습니다.

  1. 파이썬에는 mutable과 immutable 클래스가 있습니다. Int형은 immutable이므로 x += 1을 할 때 단순히 x에 있는 값에 1을 더하는 개념이 아니라 새로운 object를 생성하는 것입니다(실제로는 그렇지는 않습니다). 즉 x에 새로 생긴 object를 할당하는 구조입니다. 왜냐하면 x는 Int형으로 선언되어 immutable이고 immutable은 값 자체를 변경 불가능하기 때문입니다.
  2. python 컴파일러는 scope 내부의 모든 할당을 체크하여 모든 변수가 그 scope내에서 지역적으로 처리되게 만들어줍니다.
  3. 그래서 x를 증가시키려고 할 때에 컴파일러는 변수에 접근하게되고 해당 변수가 그 scope내의 지역변수로 인식되어 할당되지 않은 값으로 정의됩니다.

  위의 말을 제 코드에 적용시켜 생각해보겠습니다. 제가 한 착각은 컴파일러가 위에서 부터 해석해서 내려오며 max_day를 변수로 할당하고 아래에 bfs에서 해당 변수를 인지한다고 생각한 것이었습니다. 하지만 파이썬 컴파일러는 bfs를 컴파일하며 내부에서 할당된 max_day를 관찰할 때, 해당 변수를 immutable 값이므로 지역적으로 처리합니다. 그렇게되면 bfs 내에서 max_day는 할당된 적이 없기 때문에 문제가 발생합니다. 단순히 못찾는다의 오류 메세지가 아닌 지역 변수 에러를 발생시킵니다. 그렇기 때문에 bfs 내부에 변수가 아니라 전역적으로 선언되있는 변수 max_day를 가져오겠다는 global 선언을 해줍니다. 반면 visited나 tomato의 경우 mutable한 변수이기 때문에 global 선언 없이도 변경 가능합니다.

  immutable = 0
  mutable = [1, 2, 3, 4, 5] # mutable이므로 이 scope내에서 global
  
  def func_without_parameter():
      if immutable == 0 : # 에러 발생
          print(immutable)
      mutable[0] = 2
      mutable[1] = 4 
      # ...
  
  def func_with_parameter(mutable, immutable):
      if immutable == 0 : # 함수 바깥에서 선언된 immutable과 관련없는 parameter 값
          print(1)
      mutable[0] = 2 # parameter로 들어온 mutable도 이 scope 내에서 선언된 객체와 이름이 같아 같은 객체를 가르키므로 매소드 내부와 외부의 mutable 값을 다 변경시킵니다. 이 함수를 실행시킨 후 함수 밖에서 mutable을 실행시키면 값이 변해있는 것을 볼 수 있습니다.
      # ...
  
  def func_for_assignment():
      mutable = [2, 4, 6, 8, 10]
      # 바깥 scope의 mutable을 변화시키는게 아니라 내부에 새로은 local 객체 mutable을 생성합니다. 함수가 종료된 후 mutable을 출력하면 변화가 없습니다.

  정리하면 immutable이나 mutable이나 함수 내부에서 정의한다면 함수 scope 내부의 지역 변수로 선언됩니다. 하지만 immutable의 경우 이름이 같아도 기본적으로 함수 내부에서는 지역변수로 인식되기 때문에 함수 바깥의 요소로 사용하기 위해서는 전역변수화가 필요하고, mutable의 경우 해당 객체에 index로 접근하여 요소를 변경할 때에는 전역화 되어있는 듯 바꿔줄 수 있기 때문에 global 선언 없이도 가능합니다.

• 기존에는 visiting을 만들 때에 depth를 측정하기 위해 같은 depth 내에 있는 것을 묶으려는 노력을 하다보니 2차원 배열이 되었었습니다. 하지만 위의 풀이를 생각할 때에는 depth 자체를 parameter로 활용하고 최대값만 비교하는 식으로 적용하여 그럴 필요가 없었습니다. parameter를 잘 활용하면 구조가 훨씬 간편해질 수 있습니다.

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

https://stackoverflow.com/questions/21456739/unboundlocalerror-local-variable-l-referenced-before-assignment-python