[CLASS 3]백준 - 7576번, 7569번 - 토마토

7576번 : 토마토

 

심심하다 싶으면 나오는 bfs문제이다. bfs말고 dfs문제좀 풀어보고 싶다.

 

이전까지 내가 풀어온 bfs문제와 좀 다른게 있다면 시작점이 정해져 있지 않고 퍼져 있다는 점이다.

 

내 코드(정답이지만 채점오류 같음):

# dawitblog.tistory.com
from sys import stdin
from collections import deque


dx = [0,0,1,-1]
dy = [1,-1,0,0]
def tomato_bfs(box,queue):
    global changed
    while queue:
        tx,ty = queue.popleft()

        for i in range(4):
            x = tx + dx[i]
            y = ty + dy[i]

            if 0<= x < c and 0<= y < r:
                if box[y][x] == 0 or box[ty][tx] + 1 < box[y][x]:
                    changed = True
                    box[y][x] = box[ty][tx] + 1
                    queue.append((x,y))


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

# 더 익은 사과가 하나라도 있는지 확인
changed = False
queue = deque([])
for y in range(r):
    for x in range(c):
        if box[y][x] == 1:
            queue.append((x,y))

# bfs
tomato_bfs(box,queue)

# 한번도 바뀌지 않았다면
if not changed:
    print(0)
else:
    maxDay = 0
    for y in range(r):
        for x in range(c):
            if not box[y][x]:
                print(-1)
                exit()
            maxDay = max(maxDay,box[y][x])
    print(maxDay-1)

 

이 코드로 제출했는데 맞았다. 근데 좀 이상하다. 문제에서는 분명히 저장될 때부터 모든 토마토가 익어 있을 경우에 0을 출력해야 하는데 내 코드는 만약 모든 토마토가 익지 않은 날 토마토일 경우에도 0을 출력하는데 정답처리 되었다. 이에 대해서 이 다음 3차원 토마토 문제에 정정 요청을 올려놓았다.

 

# 21/04/25 관리자분께서 채점 데이터를 늘려주셔서 이제 제대로 채점이 가능하다.덤으로 문제에 내 아이디도 찍혔다!

 

어쨌든 제대로된 코드는 다음과 같다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
from collections import deque


dx = [0,0,1,-1]
dy = [1,-1,0,0]
def tomato_bfs(box,queue):
    global changed
    while queue:
        tx,ty = queue.popleft()

        for i in range(4):
            x = tx + dx[i]
            y = ty + dy[i]

            if 0<= x < c and 0<= y < r:
                if box[y][x] == 0 or box[ty][tx] + 1 < box[y][x]:
                    changed = True
                    box[y][x] = box[ty][tx] + 1
                    queue.append((x,y))


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

# 익지 않은 토마토가 하나라도 있는지 확인
anyRawTomato = False
queue = deque([])
for y in range(r):
    for x in range(c):
        if box[y][x] == 1:
            queue.append((x,y))
        elif box[y][x] == 0:
            anyRawTomato = True

# bfs
tomato_bfs(box,queue)

# 처음에 모두 익은 토마토였다면
if not anyRawTomato:
    print(0)
else:
    maxDay = 0
    for y in range(r):
        for x in range(c):
            if not box[y][x]:
                print(-1)
                exit()
            maxDay = max(maxDay,box[y][x])
    print(maxDay-1)

 

처음에 모든 칸을 조사할때 익지 않은 토마토가 하나 이상 있었는지 검사해주어야 한다.

 

7569번 : 토마토

 

이 문제는 아까 문제에서 더 발전한 3차원 토마토 문제이다.

 

제대로 bfs를 안돌리고 헛계산 하는 코드를 만들면 시간 초과에 걸려버리니 주의해야 한다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
from collections import deque
input = stdin.readline

def tomato_bfs(boxes,queue):
    global changed
    dx = [0,0,0,0,1,-1]
    dy = [0,0,1,-1,0,0]
    dz = [1,-1,0,0,0,0]

    while queue:
        tx,ty,tz = queue.popleft()
        for i in range(6):
            newX = tx + dx[i]
            newY = ty + dy[i]
            newZ = tz + dz[i]

            # 상자를 벗어나지 않는다면
            if 0<=newX<c and 0<=newY<r and 0<=newZ<h:
                if boxes[newZ][newY][newX] == 0 or boxes[tz][ty][tx]+1<boxes[newZ][newY][newX]:
                    # 한번이라도 새로 익은 토마토가 있는지 확인
                    changed = True
                    boxes[newZ][newY][newX] = boxes[tz][ty][tx]+1
                    queue.append((newX,newY,newZ))

c,r,h = map(int,input().split())
boxes = [[list(map(int,input().split())) for _ in range(r)] for _ in range(h)]

anyRawTomato = False 
queue = deque([])
for z in range(h):
    for y in range(r):
        for x in range(c):
            # 처음부터 익어있던 토마토를 만났을 경우
            if boxes[z][y][x] == 1:
                queue.append((x,y,z))
            elif boxes[z][y][x] == 0:
                # 초기에 날것의 토마토가 하나라도 있다면
                anyRawTomato = True

# bfs
tomato_bfs(boxes,queue)

# 처음에 모두 다 익은 토마토였다면
if not anyRawTomato:
    print(0)
else:
    maxDay = 0
    # 안익은 토마토가 하나라도 있는지 확인
    for z in range(h):
        for y in range(r):
            for x in range(c):
                if not boxes[z][y][x]:
                    print(-1)
                    exit()
                maxDay = max(maxDay,boxes[z][y][x])

    # 가장 오래 걸리는 시간 출력
    print(maxDay-1)

 

3차원이라고 다른건 없고 그냥 3차원 배열이 된다. 하다보면 좀 헷갈릴수 있는데 그런것만 주의하면 된다.