백준 7569 토마토 골드5 (BFS)

 

 

문제 설명

- 가로 M, 세로 N, 높이 H의 토마토 상자

- 보관 후 하루가 지나면 익은 토마토의 위, 아래, 왼쪽, 오른쪽, 앞 뒤 여섯 방향의 토마토는 익는다

- 보관된 토마토들이 모두 익는데 소요되는 최소 일수

입력값

1. M, N, H ( 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 )

2. N개의 줄까지 하ㅏ의 상자에 담긴 토마토의 정보

- 1은 익은 토마토 0은 안익은 토마토 -1은 빈 공간

- 토마토가 하나 이상 익은 경우만 입력으로 주어진다

출력값

- 토마토가 모두 익는데 걸리는 최소 일수

- 저장될 때부터 모두 익어있으면 0 출력

- 토마토가 모두 익지 못하는 상황이면 -1

 

---

종합 결과

 

 

 

첫번째 시도

import copy

def mature(h,r,c) :
    global time, time_tomato, tomato, H

    check = 0       # 고립 확인

    # 상우하좌
    dr,dc = [-1,0,1,0],[0,1,0,-1]

    for k in range(4) :
        if 0 <= r+dr[k] < R and 0<= c+dc[k] < C :
            if tomato[h][r+dr[k]][c+dc[k]] == -1 :
                check += 1 
            elif tomato[h][r+dr[k]][c+dc[k]] == 0:  # 익히지 않은 토마토
                time_tomato[h][r+dr[k]][c+dc[k]] = 1

    # 아래층
    if 0 <= h-1 :
        if tomato[h-1][r][c] == -1 :
            check += 1
        elif tomato[h - 1][r][c] == 0:
            time_tomato[h-1][r][c] = 1
             
    # 위층
    if h+1 < H :
        if tomato[h+1][r][c] == -1 :
            check += 1
        elif tomato[h + 1][r][c] == 0:
            time_tomato[h+1][r][c] = 1
     
    if check == 6 :
        time = -1       # 고립된 값이 있는 상태





C,R,H = map(int,input().split())
time = 0

tomato = [[] for _ in range(H)]
for i in range(H) :
    tomato[i] = [list(map(int,input().split())) for _ in range(R)]


time_tomato = copy.deepcopy()

while True :

    need = C*R*H             # need_mature

    for f in range(H) :     # floor
        for i in range(R) :
            for j in range(C) :
                if tomato[f][i][j] == 1 :
                    need -= 1
                    mature(f,i,j)
                    if time == -1 :
                        break
                elif tomato[f][i][j] == -1 :
                    need -= 1

    if need == 0 :
        break

    tomato = time_tomato.copy()
    time += 1


print(time)

 

• 처음엔 간단한 문제라고 생각하고 시작해서 하드코딩이 되어버림
• 0 이상의 값이 나오는 경우 올바르게 처리되지만, 
• 토마토가 고립된 경우(-1 값)을 처리하는게 어려움
• 또한 시간초과로 답도 안나옴

 

---

 

 

두번째 시도 : BFS

from collections import deque

def bfs() :
    
    q = deque()

    # 방향 저장(h,r,c) 위아래 상하좌우
    direction = [(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1)]


    # 익은 토마토 찾기
    for h in range(H) :
        for r in range(R) :
            for c in range(C) :
                if tomato[h][r][c] == 1 :
                    q.append((h,r,c,0))       # 0 : 시간


    # 토마토 숙성시키기
    while q :
        h, r, c, time = q.popleft()
        
        for dh,dr,dc in direction :
            nh,nr,nc = h+dh, r+dr, c+dc
            if 0<= nh < H and 0<= nr < R and 0<= nc < C and tomato[nh][nr][nc] == 0 :
                tomato[nh][nr][nc] = 1
                q.append((nh,nr,nc,time+1)) 


    # 탐색 끝나면 숙성안된 토마토가 남았는지 확인
    for h in range(H) :
        for r in range(R) :
            for c in range(C) :
                if tomato[h][r][c] == 0 :       # 고립된 토마토가 있다는 뜻
                    return -1
    
    return time



# 입력 처리
C, R, H = map(int, input().split())  # 열, 행, 층 개수 입력
# 3차원 배열로 토마토 상태 입력 받음
tomato = [ [list(map(int, input().split())) for _ in range(R)] for _ in range(H) ]

# BFS를 수행하여 결과 출력
print(bfs())

 

 

• 224392KB, 672ms(PyPy3) 으로 성공

   

from collections import deque

def bfs():
    global time
    # 6방향(위, 아래, 왼쪽, 오른쪽, 앞, 뒤)을 표현하는 방향 벡터
    directions = [
        (-1, 0, 0),  # 아래층
        (1, 0, 0),   # 위층
        (0, -1, 0),  # 왼쪽
        (0, 1, 0),   # 오른쪽
        (0, 0, -1),  # 앞쪽
        (0, 0, 1)    # 뒤쪽
    ]
    
    # BFS 탐색에 사용할 큐를 생성
    queue = deque()

    # 초기 상태에서 익은 토마토(1)의 위치를 큐에 추가
    for h in range(H):       # 층 반복
        for r in range(R):   # 행 반복
            for c in range(C):  # 열 반복
                if tomato[h][r][c] == 1:
                    # 큐에 (층, 행, 열, 현재 시간) 추가
                    queue.append((h, r, c, 0))

    # BFS 탐색 시작
    while queue:
        h, r, c, time = queue.popleft()  # 큐에서 가장 앞의 위치 정보 꺼냄

        # 6방향 탐색
        for dh, dr, dc in directions:
            nh, nr, nc = h + dh, r + dr, c + dc  # 새 좌표 계산
            
            # 유효 범위 내에 있고, 익지 않은 토마토(0)일 경우
            if 0 <= nh < H and 0 <= nr < R and 0 <= nc < C and tomato[nh][nr][nc] == 0:
                tomato[nh][nr][nc] = 1  # 익은 상태로 갱신
                queue.append((nh, nr, nc, time + 1))  # 큐에 새 위치와 시간 추가
    
    # 탐색 종료 후, 익지 않은 토마토가 있는지 확인
    for h in range(H):
        for r in range(R):
            for c in range(C):
                if tomato[h][r][c] == 0:  # 익지 않은 토마토가 있다면
                    return -1  # 고립 상태이므로 -1 반환
    return time  # 마지막으로 업데이트된 시간 반환

# 입력 처리
C, R, H = map(int, input().split())  # 열, 행, 층 개수 입력
# 3차원 배열로 토마토 상태 입력 받음
tomato = [ [list(map(int, input().split())) for _ in range(R)] for _ in range(H) ]

# BFS를 수행하여 결과 출력
print(bfs())

• 이해가 안되면 위의 자세한 주석 코드를 참고하면 된다
• sys.stdin.readline 을 해서 시간을 줄여보려했으나,
• 결과는 223848KB, 684ms(PyPy3)로 유의미한 차이가 없었다

 

다른사람 풀이 공부 : 2차원 리스트

# 2차원 리스트로 만들어 풀이하는 방법

from collections import deque
import sys
input=sys.stdin.readline

# 입력 받기
M, N, H = map(int, input().split())  # M: 가로 칸 수, N: 세로 칸 수, H: 상자의 높이
boxes = [list(map(int, input().split())) for _ in range(N * H)]  # 전체 토마토 상자 정보 (2차원 리스트로 연결)

all_row = N * H  # 총 행의 개수 (세로 방향 + 층 개수 포함)
dx = [1, -1, 0, 0, N, -N]  # 이동 방향: 오른쪽, 왼쪽, 아래, 위, 윗층, 아랫층
dy = [0, 0, 1, -1, 0, 0]   # 이동 방향: x방향은 그대로, y방향은 오른쪽/왼쪽만

ripen_tomatos = deque()  # 익은 토마토의 위치를 저장하는 큐
unripe = 0               # 익지 않은 토마토의 개수

# 초기 상태 확인
for i in range(all_row):  # 전체 행 탐색
    for j in range(M):    # 각 행의 열 탐색
        if boxes[i][j] == 1:  # 익은 토마토인 경우
            ripen_tomatos.append((i, j))  # 큐에 위치 추가
        if boxes[i][j] == 0:  # 익지 않은 토마토인 경우
            unripe += 1  # 익지 않은 토마토 개수 증가

# 익지 않은 토마토가 없다면
if unripe == 0:
    print(0)  # 이미 모두 익어있으므로 0일 출력

else:
    day = -1  # 날짜 초기화 (첫날 0일을 만들기 위해 -1로 시작)

    # BFS로 토마토 익히기
    while ripen_tomatos:  # 익은 토마토가 있는 동안 반복
        day += 1  # 날짜 증가
        for _ in range(len(ripen_tomatos)):  # 현재 익은 토마토들만 처리
            x, y = ripen_tomatos.popleft()  # 익은 토마토의 위치 꺼내기
            
            for i in range(6):  # 6방향 탐색
                # 2차원 리스트에서 위아래로 넘어가는 경우 방지 (N으로 나눈 나머지를 이용)
                if (i == 0 and x % N == N - 1) or (i == 1 and x % N == 0):
                    continue  # 오른쪽에서 다음 행으로 넘어가는 경우, 왼쪽에서 이전 행으로 넘어가는 경우 스킵

                nx, ny = dx[i] + x, dy[i] + y  # 다음 위치 계산
                # 범위 내에 있으면서 익지 않은 토마토라면
                if 0 <= nx < all_row and 0 <= ny < M and boxes[nx][ny] == 0:
                    boxes[nx][ny] = 1  # 토마토를 익힘
                    ripen_tomatos.append((nx, ny))  # 새로운 익은 토마토 위치 추가
                    unripe -= 1  # 익지 않은 토마토 개수 감소

    # 모든 토마토가 익었는지 확인
    print(day if unripe == 0 else -1)  # 모두 익었으면 걸린 날짜, 그렇지 않으면 -1 출력

 

•  2차원 리스트로 풀이하신 분이 있어서  코드 분석을 해보았다
• 143232KB, 420ms(PyPy3) 로 시간과 메모리 면에서 압도적이다

 

코드 업그레이드 시도

# 223348KB, 692ms(PyPy3) 
# unripen 추가하여 속도 향상 기대!
# 했지만 더 느려짐

import sys
from collections import deque

input = sys.stdin.readline

def bfs() :
    
    q = deque()

    # 방향 저장(h,r,c) 위아래 상하좌우
    direction = [(-1,0,0),(1,0,0),(0,-1,0),(0,1,0),(0,0,-1),(0,0,1)]


    unripe = 0

    # 익은 토마토 찾기
    for h in range(H) :
        for r in range(R) :
            for c in range(C) :
                if tomato[h][r][c] == 1 :
                    q.append((h,r,c,0))       # 0 : 시간
                elif tomato[h][r][c] == 0 :
                    unripe += 1
    
    if unripe == 0 :
        return 0


    # 토마토 숙성시키기
    while q :
        h, r, c, time = q.popleft()
        
        for dh,dr,dc in direction :
            nh,nr,nc = h+dh, r+dr, c+dc
            if 0<= nh < H and 0<= nr < R and 0<= nc < C and tomato[nh][nr][nc] == 0 :
                tomato[nh][nr][nc] = 1
                q.append((nh,nr,nc,time+1)) 


    # 탐색 끝나면 숙성안된 토마토가 남았는지 확인
    for h in range(H) :
        for r in range(R) :
            for c in range(C) :
                if tomato[h][r][c] == 0 :       # 고립된 토마토가 있다는 뜻
                    return -1
    
    return time



# 입력 처리
C, R, H = map(int, input().split())  # 열, 행, 층 개수 입력
# 3차원 배열로 토마토 상태 입력 받음
tomato = [ [list(map(int, input().split())) for _ in range(R)] for _ in range(H) ]

# BFS를 수행하여 결과 출력
print(bfs())

 

• 위 코드를 모두 이해하긴 어려워서,
• 이미 모두 익어있는 경우를 확인할 수 있도록 unripe 를 추가해서 시도해보았지만
• 오히려 속도가 느려지기만 했다