BOJ #7569 토마토

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 7569. 토마토

문제 풀이

BFS 풀이 심화문제다. 3차원으로 배열이 확장되었을 뿐 풀이 자체는 그리 어렵진 않다. 다만 주의할 점으로는 별도로 토마토가 익어가는 시간만 체크할 수 있으면 기존 BFS, DFS 풀이처럼 방문했던 경로를 마킹하는 별도의 리스트를 생성할 필요가 없다는 점이다. 만약 별도의 리스트를 생성했다면 TLE(Time Limit Error)를 출력한다.

python 코드 - 1

from sys import stdin
from collections import deque
input = stdin.readline
 
M, N, H = map(int, input().split()) # x, y, z, 좌표 입력
board = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
q = deque() # 큐 생성
for h in range(H):
    for r in range(N):
        cols = list(map(int, input().split()))
        for c, x in enumerate(cols):
            board[h][r][c] = x
            if x == 1: # 만약 익은 토마토라면
                q.append([h, r, c, 0]) # 큐에 좌표값, 날짜 입력
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
sol = 0
while q: # BFS 탐색 시작
    z, y, x, c = q.popleft()
    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        nc = c + 1
        if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and board[nz][ny][nx] == 0:
            # 만약 좌표가 범위내고 해당 좌표의 상태가 익지 않은 토마토라면
            board[nz][ny][nx] = 1 # 익었다고 마킹
            q.append([nz, ny, nx, nc]) # 큐에 추가
            sol = nc # 날짜 1 증가
zero = False
for z in range(H):
    for y in range(N):
        if 0 in board[z][y]:
            sol = -1
            zero = True
            break
    if zero: # 이중 for문 break
        break
print(sol)

이 코드는 통과한 코드인데 여기서 조금 배운 점이 있었다. 위 코드와 로직이 정확히 동일한 코드였지만 단지 x, y, z 좌표를 이동할 때 하나의 리스트에 6가지 케이스([[0,0,1],[0,0,-1],...,[-1,0,0]] 형태의 리스트)를 담아서 매번 조회하는 코드를 제출한 결과 TLE가 발생하였다. python에서는 range로 정수범위 반복문을 호출하지 말고 완성된 list에서 원소 각각에 대해 접근을 권장하지만 시간 제한이 걸린 PS에서는 위 방법대로 정수 범위의 반복문을 선언한 뒤 좌표값으로 접근해야 할 것이다.

python 코드 - 2

from sys import stdin
from collections import deque
input = stdin.readline
 
M, N, H = map(int, input().split())
board = [[[0 for _ in range(M)] for _ in range(N)] for _ in range(H)]
q = deque()
for h in range(H):
    for r in range(N):
        cols = list(map(int, input().split()))
        for c, x in enumerate(cols):
            board[h][r][c] = x
            if x == 1:
                q.append([h, r, c, 0])
dx = [1, -1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
 
def bfs(sol):
    while q:
        z, y, x, c = q.popleft()
        for i in range(6):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = z + dz[i]
            nc = c + 1
            if 0 <= nx < M and 0 <= ny < N and 0 <= nz < H and board[nz][ny][nx] == 0:
                board[nz][ny][nx] = 1
                q.append([nz, ny, nx, nc])
                sol = nc
    return sol
 
def check(sol):
    for z in range(H):
        for y in range(N):
            if 0 in board[z][y]:
                return -1
    return sol
 
sol = bfs(0)
print(check(sol))

혹시나 해서 위 코드와 매우 똑같은 코드지만 함수로 감싸서 제출한 결과 속도가 거의 20%는 빨라졌다. PS의 경우 TLE가 걱정되는 탐색 문제라면 아예 함수로 제출하는 경우의 수도 고려해야겠다. 1번 코드는 5000ms였지만 2번 코드는 3800ms로 함수로 제출했을 뿐임에도 속도가 상당히 개선되었다.