[Python] 백준 7576 토마토

 

문제 분석

• 가로 m, 세로 n
• 잘 익은 토마토 & 안 익은 토마토
• 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익음
• 인접 = 상하좌우
• 토마토가 혼자 익는 경우는 x
• 며칠이 지나면 다 익게 되는지 최소 일수를 알고 싶다.

• 1 : 익은 토마토
• 0 : 익지 않은 토마토
• -1 : 빈 칸

• 저장될 때 부터 모든 토마토가 익어있으면 0 리턴
• 모두 익지 못하는 상태이면 -1 리턴

 

코드 설계

• 넓이 우선 탐색 (bfs)
• 박스 안에 0이 있지 않으면 return

• 종료 조건 1
  • 모든 토마토가 익었을 때
  • if 0 not in box
  • 박스에 
• 종료 조건 2
  • 모두 익지 못하는 상태
  • 모든 1 주변에 0이 없는 경우

• 1을 싹다 찾고
• 상하좌우에 0이 있는지 확인
• 주변에 0이 있는 1 중 주변의 0이 1로 바뀌면 
• 동시 다발적으로 하루가 지나면 주변이 싹 익음
• 이거를 박스 안에 0이 없을때 까지 반복
• bfs를 어떻게 이용할 것인가

• 1을 다 찾고
• 1의 개수만큼 반복문을 돌아서 
• 1 주변의 0을 다 1로 바꾸면 다시 1 찾기
• 만약 이 중 1의 주변(상하좌우)에 0이 없으면 -1 출력하고 끝

 

정답 코드

1차 - 시간 초과

import sys
input = sys.stdin.readline

from collections import deque

m, n = map(int, input().split())  # m : 가로, n : 세로
box = []
for _ in range(n):
    box.append(list(map(int, input().split())))
day = 0

d = deque()
dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

'''
def isRipe(b) :
    for i in range(n) :
        for j in range(m) :
            if b[i][j] == 0 :
                return False
    return True
'''

def isRipe(b) :
    for t in b :
        if 0 in t :
            return False
    return True
    
def bfs(dq):  # 1주변의 0 찾기
    h, w = dq.popleft()
    check = 0 # 1주변에 0이 있는지 확인

    for k in range(4):
        nh = h + dh[k]
        nw = w + dw[k]

        if nh < 0 or nh >= n or nw < 0 or nw >= m:
            continue
        if box[nh][nw] != 0:
            continue

        check += 1
        box[nh][nw] = 1

    if check == 0 : # 만약 1 주변에 0이 없으면 0 리턴
        return 0

    return 1

while True:
    # 종료조건1 : 모든 토마토가 익었을 때
    if isRipe(box):
        print(day)
        break
    # 종료조건2 : 모두 익지 못하는 상태

    # 1을 찾으면 bfs()에 넣어서 상하좌우 탐색
    ripe_tomato = []  # 새로 1 찾기
    for i in range(n):
        for j in range(m):
            if box[i][j] == 1:
                ripe_tomato.append((i, j))

    check = 0
    for t in ripe_tomato:
        d.append(t)
        check += bfs(d) # 상하좌우 탐색해서 1로 만들기

    if check == 0 :
        print(-1)
        break
    day += 1 # 1 주변 0을 다 1로 바꾸면 하루가 지남

이걸 bfs를 했다고 할 수 있나..?

 

다른 사람 코드 1

https://velog.io/@hamsangjin/%EB%B0%B1%EC%A4%80-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

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

m, n = map(int, input().split())
box = []

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

for _ in range(n) :
    box.append(list(map(int, input().split())))

d = deque()

for i in range(n) :
    for j in range(m) :
        if box[i][j] == 1 :
            d.append((i,j))

while d :
    for _ in range(len(d)) : # 큐에 삽입된 익은 토마토의 수 만틈
        h, w = d.popleft()

        # 익은 토마토의 인접한 토미트들과 비교
        for i in range(4) :
            nh = h + dh[i]
            nw = w + dw[i]

            if nh<0 or nh>=n or nw<0 or nw>m :
                continue
            if box[nh][nw] != 0 :
                continue

            # box[nh][nw] = 1
            box[nh][nw] = box[h][w] + 1

            # 익은 토마토를 다시 큐에 삽입
            d.append((nh, nw))

day = 0
for row in range(n) :
    for tomato in row :
        if tomato == 0 : # bfs를 다 돌았는데도 토마토가 다 익지 않은 경우
            print(-1)
            exit(0)
    day = max(day, max(row)) # 토마토 중 가장 큰 값 (소요일) 찾기

print(day - 1) # 익은 토마토의 초기값이 1이기 때문에 -1

 

다른 사람 코드 2

https://choihjhj.tistory.com/entry/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0

from collections import deque
M, N = map(int, input().split())
arr = []
queue = deque()
for i in range(N):
    row = list(map(int, input().split()))
    arr.append(row)
    for j in range(M):
        if row[j] == 1: #익은 토마토 덱에 위치 넣기
            queue.append((i, j))

d = d=[(-1,0),(1,0),(0,-1),(0,1)] #상하좌우
def bfs():  
    while queue: #토마토 다 익힐때까지 반복 (0없애기)
        x, y = queue.popleft()
        for i in range(4):
            nx = x + d[i][0]
            ny = y + d[i][1]
            if 0 <= nx < N and 0 <= ny < M and arr[nx][ny] == 0: #다음 위치가 안익은 토마토이면 익혀나가기
                arr[nx][ny] = arr[x][y] + 1
                queue.append((nx, ny)) #이것도 익은거니까 덱에 위치 넣기
bfs()
def get_day():
    result = 0 #결과
    for row in arr:
        if 0 in row: #안익은토마토 하나라도 있으면 -1
            return -1

        row_max = max(row)    
        if result < row_max:
            result = row_max
    return result - 1 #며칠 걸리냐 했으니까 -1 빼야 함 
print(get_day())
출처: https://choihjhj.tistory.com/entry/백준파이썬-7576번-토마토 [개발 블로그:티스토리]

 

---

 

2회차 - 25.03.11

• 익지 않은 토마토는 주변의 익은 토마토의 영향을 받아 익는다.
• 주변 : 상하좌우
• 창고에 보관된 토마토들이 며칠이 지나면 다 익는지 알고 싶다. (최소 일수)
• n, m : 상자의 크기
• 토마토 정보
  • 0 : 안익은 토마토
  • 1 : 익은 토마토
  • -1 : 토마토가 들어있지 않은 칸
• 모든 토마토가 익어있는 상태라면 0 
• 토마토가 모두 익지 못하는 상황이면 -1

 

• 경우 1. 모든 토마토가 익은 상태 : 1과 -1만 존재
• 경우 2. 다 익지 않은 상태
  • 경우 2-1. 토마토가 모두 익지 못하는 상황
    • -1로 둘러 쌓인 0
    • 0 상하좌우 -1만 있다면, print(0)
  • 경우 2-2. 익은 것들이 안익은 거를 익게 만듦

 

• 최소 날짜 → 익은 토마토들이 동시 다발적으로 주변의 익지 않은 토마토를 익게 함
  1. 우선 익은 토마토를 찾기
  2. 익은 토마토들 상하좌우 주변 안익은 토마토 익게 하기
  3. 익은 토마토 전체 찾기를 1번 할 때마다 하루가 지남
  4. 언제까지? 모든 익을 수 있는 토마토가 익을 때까지 (0이 없을 때까지)
     이전에 토마토가 모두 익지 못하는 상황은 거름

 

1차 : 완탐 - 시간 초과

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

n,m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

def cantRipe(h, w) :
    for i in range(4):
        nh = h + dh[i]
        nw = w + dw[i]

        if nh < 0 or nh >= m or nw < 0 or nw >= n:
            continue
        if g[nh][nw] != -1:
            return False
    return True # 상하좌우가 -1로 막혔으면

def allRipe(g_tomato) : # 다 익음
    all_ripe = 0
    for i in range(m):
        if not 0 in set(g_tomato[i]):
            all_ripe += 1
    if all_ripe == m:
        return True
    return False

def makeRipe(h,w) :
    global g
    for i in range(4) :
        nh = h + dh[i]
        nw = w + dw[i]

        if nh < 0 or nh >= m or nw < 0 or nw >= n :
            continue
        if g[nh][nw] == 0 :
            g[nh][nw] = 1


# 1. 다 익어 있는경우 : 1과 -1만 있는 경우
if allRipe(g) :
    print(0)
    exit(0)


# 2. 다 익을 수 없는 경우
for r in range(m):
    for c in range(n) :
        if g[r][c] == 0 :
            if cantRipe(r,c) :
                print(-1)
                exit(0)

day = 0
# 3. 모든 토마토가 익을 수 있는 경우
while not allRipe(g) :
    d_tomatoes = deque() # 익은 토마토 담기
    for r in range(m):
        for c in range(n) :
            if g[r][c] == 1 :
                d_tomatoes.append((r,c))
    while d_tomatoes : # 주변 토마토 익히기
        h,w = d_tomatoes.popleft()
        makeRipe(h,w)

    # 주변 토마토 다 익게 만들면
    day += 1

print(day)

매번 익은 토마토를 찾으므로, 이미 익은걸 확인하고 주변을 익게 만든 토마토도 다시 체크하므로 코드가 비효율적이다.

익은 토마토를 다 bfs에 넣으면 너비 우선 탐색이기 때문에 한번 주변을 탐색할 때마다 하루가 지남

 

2차

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

d = deque() # 익은 토마토 담기

for r in range(m) :
    for c in range(n) :
        if g[r][c] == 1 :
            d.append((r,c))

def bfs() :
    days = -1 # 첫날 -1

    while d :
        for _ in range(len(d)) :
            h,w = d.popleft()

            for i in range(4) :
                nh = h + dh[i]
                nw = w + dw[i]

                if 0 <= nh < m and 0 <= nw < n and g[nh][nw] == 0: # 범위안에 있다면
                    g[nh][nw] = 1 # 주변 토마토 익고
                    d.append((nh, nw)) # 새로 익은 토마토 넣기
        days += 1

    for row in g :
        if 0 in row :
            return -1
    return days

print(bfs())

 

3회차 - 25.03.14

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

m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]

dh = [-1, 1, 0, 0]
dw = [0, 0, -1, 1]

d = deque()

# 이미 다 익어있다면 day = 0
# check = 0
# for i in range(n) :
#     if 0 not in box[i] :
#         check += 1
# if check == n :
#     print(0)
#     sys.exit(0)

# 우선 토마토 싹 다 넣기
for i in range(n) :
    for j in range(m) :
        if box[i][j] == 1 :
            d.append((i, j))

def dfs() :
    day = -1
    '''
    왜 day = -1로 시작?
        익은 토마토를 모두 덱에 넣어둔 상태에서 시작
        -> 첫번째 반복에서는 주변의 익지 않은 토마토에 대한 너비우선탐색을 하므로
        아무 변화도 없이 기존 익은 토마토만 처리
    '''
    while d :
        for _ in range(len(d)) :
            h, w = d.popleft() # 1 토마토를 기준으로

            # 상하좌우 안익은 토마토 덱에 넣기
            for k in range(4) :
                nh = h + dh[k]
                nw = w + dw[k]

                if (0<=nh<n and 0<=nw<m) and box[nh][nw] == 0 :
                    box[nh][nw] = 1
                    d.append((nh, nw))
        day += 1
    
    # 처음부터 다 익었다면 새로 append되지 않고 그냥 day += 1
    # 따라서 L13~20 부분을 따로 구현하지 않아도 된다.
    
    # 나왔는데 다 익지 못햇으면 -1
    for i in range(n) :
        if 0 in box[i] :
            day = -1
    
    return day

print(dfs())