[ Baekjoon 백준 ] # 7569 번 Python 풀이

 

 

// 문제 요약

 

토마토를 3차원 격자에 배치한다.

 

익은 것, 안 익은 것, 빈 칸 이렇게 세 종류의 칸이 존재한다.

 

익은 토마토의 대각선 방향을 제외한 이웃한 칸에

 

안 익은 토마토가 있을 경우 하루가 지나면 익은 토마토로 바뀐다고 할때

 

토마토가 다 익는데 걸리는 최소 일자를 구해라

 

단 모든 토마토가 익을 수 없다면 -1을

 

처음부터 모두 익어있다면 0을 출력해라.

 

 

// 사고

 

3차원에 덜컥 겁을 먹었는데 알고보니 원래 2차원 문제였던걸 확장한 문제여서

 

2차원 문제 풀었던 사람들은 쉽게 접근을 했던 문제였다.

 

역시 코테는 문제를 얼마나 풀어보느냐가 절반은 먹고 들어간다.

 

아무튼 시간이 많이 걸리겠다 생각이 들어서 백트래킹을 생각할 수 있는데

 

백트래킹은 DFS 이므로 하루에 이웃한 한 칸만 전염시키는 조건에 맞풀 수 없다.

 

즉 1회 시행에 탐색할 수 있는 인접한 모든 노드를 탐색하는 BFS가 맞는 풀이다.

 

그리고 시행 횟수를 출력하면 된다.

 

백준은 플랫폼의 특성상 모든 입출력을 io 형태로 받고 해석해야하는데

 

이 과정은 어차피 부르트 포스 이므로 이 과정을 거치면서 얻을 수 있는 정보를

 

최대한 얻어내서 이용하는 전략을 취했다.

 

다시 말해, 모든 토마토의 상태를 입력으로 받으면서

 

익었으면 위치를 기억하고

 

안익었으면 수를 카운트하고

 

비었으면 아무일도 하지 않는 방식으로 전처리하였다.

 

그리고 기억한 위치들을 모두 꺼내서 전염시킨 후 하루를 카운트하고

 

전염이 발생할때마다 안익은 토마토의 수를 1씩 빼주었다.

 

각설하고 코드를 보자.

 

 

//풀이

 

https://github.com/hyun06000/coding_test_study_with_python/blob/main/Baekjoon/7569.py

hyun06000/coding_test_study_with_python

 

 

from collections import deque

def infect(q, i, j, k):
    global boxes, zero_tomatos

    # 상자 밖으로 가면 중단
    if i >= H or j >= N or k >= M:
        return
    if i < 0 or j < 0 or k < 0:
        return

    if not boxes[i][j][k][1]:         # 방문 기록 없으면
        boxes[i][j][k][1] = True      # 방문 기록

        if not boxes[i][j][k][0]:     # 안익은 토마토
            boxes[i][j][k][0] = 1     # 상태 변화
            zero_tomatos -= 1         # 안익은 토마토 총량 감소
            q.append([i, j, k])       # 이제 익은 토마토니까 큐에 추가

        elif boxes[i][j][k][0] == 1:  # 익은 토마토
            q.append([i, j, k])       # 변화 없이 큐에 추가
        else:                         # 토마토 없음
            pass                      # 아무것도 하지마
    return


M, N, H = map(int, input().split(' '))

zero_tomatos = 0
one_tomatos = boxes = []
for h in range(H):
    box = []
    for n in range(N):
        row = []
        for m, tomato in enumerate(input().split(' ')):
            tomato = int(tomato)

            if not tomato: # 안익은 토마토
                zero_tomatos += 1 # 전체 상자의 안익은 토마토 갯수
                row.append([tomato, False]) # [토마토 상태, 방문 기록]
            elif tomato == 1: # 익은 토마토
                one_tomatos.append((h, n, m)) # 익은 토마토 위치
                row.append([tomato, True])
            else: # 토마토 없음
                row.append([tomato, False])
        box.append(row)
    boxes.append(box)

if not zero_tomatos: # 안익은 토마토 없음 -> 모든 토마토가 익은 경우
    print(0)

else:
    days = 0
    q = deque(one_tomatos)
    while q:
        q_len = len(q)
        for _ in range(q_len): # 그 전날에 감염된 애들만큼만 큐를 pop
            i, j, k = q.popleft()

            infect(q, i+1, j, k) # for 문으로 해도 좋다.
            infect(q, i, j+1, k)
            infect(q, i, j, k+1)

            infect(q, i-1, j, k)
            infect(q, i, j-1, k)
            infect(q, i, j, k-1)

        days += 1

    if zero_tomatos:  # 맨 처음 안익은 토마토 수 > 바뀐 토마토 수
        print(-1)     # -1 출력
    else:             # 아니면
        print(days-1) # q 가 비어있는지 while이 검사하도록 하루를 더 썼으므로 -1 해서 출력

 

이웃한 한칸씩 진행할때 굳이 for문으로 쓰지 않고 그냥 나열했다.

 

면접관이 물어본다면 가독성을 위해서 그랬다고 할 것이다.

 

infect 함수를 보면 역시 내가 항상 강조하는 copy 를 신경써야하는데

 

q가 함수내에서 지역변수로 재선언되지 않았고 객체의 method를 사용하므로

 

q의 주소값은 바뀌지 않고 루프를 돌때마다 이어진다.

 

그래서 여기서는 deep copy 보다는 shallow copy 를 해주는게 더 좋다.

 

그리고 익은 토마토는 전염시키지 않고 다음번 전염을 위해서 위치를 기록하는데

 

이 과정에서 방문 기록을 남기지 않으면 아무일도 일어나지 않는데

 

 q가 비워지지 않는 상태가 지속된다.

 

따라서 토마토를 담을때 방문기록을 해줌으로 이 문제를 해결할 수 있다.

 

결과는 통과였지만 더 빠르게 구현할 수 있는 방법들이 존재하는 모양이다.

 

내 코드가 그렇게 빠른 편은 아니었다.

 

아마 부르트 포스로 전처리를 해주는 방식이 그렇게 현명하지는 않았나보다.

 

참고로 이 문제의 출처가 정보 올림피아드 초등부라는 사실을 발견했다.