백준 7576번: 토마토 (Python)

7576번: 토마토

뭔가 그래프 문제를 풀어보고 싶었는데 딱 그래프같아서 한번 풀어봤다.

아래 코드는 코드를 다듬지 않고 풀었을 때 나온 코드다.

def get_surroundPos(field, pos, MW, MH):
    rPos = []
    if pos[0] - 1 >= 0:
        if field[pos[0]-1][pos[1]] == 0:
            rPos.append((pos[0]-1, pos[1]))
            field[pos[0]-1][pos[1]] = 1
    if pos[0] + 1 < MH:
        if field[pos[0]+1][pos[1]] == 0:
            rPos.append((pos[0]+1, pos[1]))
            field[pos[0]+1][pos[1]] = 1
    if pos[1] - 1 >= 0:
        if field[pos[0]][pos[1]-1] == 0:
            rPos.append((pos[0], pos[1]-1))
            field[pos[0]][pos[1]-1] = 1
    if pos[1] + 1 < MW:
        if field[pos[0]][pos[1]+1] == 0:
            rPos.append((pos[0], pos[1]+1))
            field[pos[0]][pos[1]+1] = 1
    return rPos, field

w, h = map(int, input().split())
field = []
underripe_tomato = []
for _ in range(h):
    field.append(list(map(int, input().split(' '))))
for i in range(h):
    for j in range(w):
        if field[i][j] == 1:
            underripe_tomato.append((i, j)) #pos == 리스트로 봤을때랑 같음
unripe_tomato = []
for pos in underripe_tomato:
        rPos, field = get_surroundPos(field, pos, w, h)
        unripe_tomato += rPos
underripe_tomato = list(set(unripe_tomato))
tries = 0
while underripe_tomato:
    unripe_tomato = []
    for pos in underripe_tomato:
        rPos, field = get_surroundPos(field, pos, w, h)
        unripe_tomato += rPos
    underripe_tomato = list(set(unripe_tomato))
    tries += 1
for i in range(h):
    for j in range(w):
        if field[i][j] == 0:
            tries = -1
print(tries)

해당 코드를 살펴보면 상황에 맞지 않은 함수 사용이나 중복되는 부분이 보인다.

상황에 맞지 않는 함수 사용은 get_surroundPos에서 field값을 수정해 주는 작업을 하는 것이다.

이 부분은 field값을 main에서 수정해주도록 바꿔주면 된다. (하지만 그렇게 되면 또 탐색을 해야하기 때문에 그냥 get_surroundPos를 raping이나 다른 이름으로 바꿔줄 거같다.)

중복되는 부분은 깊게 생각하지 못해 발생한 문제이다.

처음에 문제를 풀 때 토마토가 익는 과정을 거칠 필요가 없을 수도 있다는 생각을 못했다. 그래서 바로 익는 과정을 만들었는데 그렇게 되면 tries가 무조건 1이 되기때문에 전체적으로 고쳐야하는 상황이 생긴다. 

다시 풀게 된다면 과정을 나눠 문제를 풀것이다.

1. 전체 토마토 위치 체크
2. 익는 과정이 필요한가? 체크
3. 익는 과정 반복 중 - 다 익었나? 체크
4. 익지 않은 토마토가 있는가? 체크

 

w, h = map(int, input().split())
field = []

def isAllTomatoesRipe(w, h): #모든 토마토가 익었는지 체크
    for i in range(h): 
        for j in range(w):
            if field[i][j] == 0:
                return False
    return True

def riping(pos, w, h): #상하좌우 중 익을 수 있는 토마토 익게하고 그 좌표 받아오기
    x, y = pos[0], pos[1]
    rPos = []
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        new_x, new_y = x+dx, y+dy
        if 0 <= new_x and new_x<= h-1 and 0 <= new_y and new_y <= w-1:
            if field[new_x][new_y] == 0:
                field[new_x][new_y] = 1
                rPos.append((new_x, new_y))
    return rPos

ripe_tomato = []
for i in range(h): #토마토 입력 및 익은 토마토 선별
    field.append(list(map(int, input().split())))
    for j in range(w):
        if field[i][j] == 1:
            ripe_tomato.append((i, j))
count = 0
while True:
    next_ripe_tomatos = []
    for pos in ripe_tomato:
        next_ripe_tomato = riping(pos, w, h)
        next_ripe_tomatos += next_ripe_tomato
    ripe_tomato = next_ripe_tomatos
    if not ripe_tomato: #더 이상 익을 토마토가 없으면 탈출
        break
    count += 1

print(count if isAllTomatoesRipe(w, h) else -1)