Python으로 푸는 백준 7576. 토마토

백준 7576. 토마토

문제는 제시된 조건에 따라 토마토가 익어간다고 했을 때

이미 모든 토마토가 익어있으면 0을, 

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

그 외의 경우에는 모든 토마토가 익으려면 며칠이 걸리는지 그 최소 일수를 구하도록 해야 한다.

유사한 문제로 LeetCode 994. Rotting Oranges도 있다.

백준에서 푼 문제 리스트 보기

github에서 코드 보기

문제 조건

상자의 일부 칸에는 토마토가 들어 있지 않을 수도 있다(즉, 아직 안익은 토마토를 빈칸이 둘러쌓은 경우에는 토마토가 익지 않을 수도 있다)

이미 모든 토마토가 익어있을 경우에는 0을 출력해야 한다.

익은 토마토가 하나도 없는 경우에는 애초에 토마토가 모두 익지 못하는 상황이므로 -1을 출력해야 한다.

문제를 틀렸다면 체크할 사항

시간 초과

list.pop(0)의 경우에는 첫번째 원소를 반환하고 모든 원소를 앞으로 한칸씩 이동해야 하므로 O(n)만큼의 시간이 걸린다.

이 문제의 경우, 어차피 어느 토마토의 주변을 먼저 살피든 상관 없으므로 list.pop()으로 맨 마지막 원소를 반환해서 사용해 보자.

그러면 시간 복잡도가 줄어들어 시간 초과 문제는 해결할 수 있다.

문제가 틀렸습니다

모든 테스트 케이스를 검토했는데 갑자기 마지막에 틀렸다고 뜬다면! 문제에서 제시한 조건을 모두 잘 구현했는지 확인해보자. 

예를 들어, 이미 모든 토마토가 익었을 경우 0을 출력하라고 했을 때, 모든 익은 토마토의 갯수 == n * m 이라고 착각한 건 아닌지 확인해보자.

토마토 상자에는 빈 칸도 존재한다는 사실을 잊었을 경우에 채점을 다 마치고 나서 "틀렸습니다" 라고 나올 수도 있다.

문제 풀이

첫 2차원 배열에서 익은 토마토의 위치 정보를 익은 토마토 리스트에 넣어준다.

익은 토마토 리스트에서 익은 토마토 하나를 꺼내, 상하좌우 방향으로 1칸 간격에 위치한 안익은 토마토를 익게 한다. 

주변의 토마토를 익히게 했을 경우에는, 다음 타이밍에 지금 익은 토마토의 주변을 체크하기 위해서 다음에 확인할 익은 토마토 리스트 안에 집어넣는다.

익은 토마토 리스트가 비워지게 되면, 다음에 확인할 익은 토마토 리스트를 꺼내와서 다시 이 작업을 반복한다.

만약 리스트가 다 비워질 떄까지, 단 하나의 토마토도 익게 하지 못한다면 작업을 멈추고 -1을 반환한다.

리스트를 모두 확인하는 작업을 얼마나 반복해야만 모든 토마토가 익게 될지 횟수를 가산해두고 모든 토마토가 익게 되었을 때 그 값을 반환하면 된다.

문제를 풀면서 헷갈렸던 파이썬 개념

새로 알게 되었다기 보다도 이미 알았던 사실을 헷갈리는 경우가 있다.

배열의 경우에는 copy.deepcopy를 사용해야만 원소의 값만을 복사해 갈 수 있다.

안그러면 아래 보이는 예시처럼, 그냥 그 주소값에 대한 새별명을 만들어주는 것밖에는 되지 않는다. 

test = ['a','b','c']

temp = test

temp[0] = 'd'

print(temp)  # ['d','b','c']

print(test)    # ['d','b','c']

새로운 변수 temp에 배열을 복사했다고 생각했지만, 사실상 주소값이 얕은 복사된 것이기 때문에 값을 바꾸면 기존 변수의 값들도 함께 바뀐다.

결국 temp만 변경하고 싶었지만 test도 함께 값이 변경된다.

내가 헷갈렸던 것은, temp를 초기화 했을 경우에 test도 초기화 되는게 걱정이었다. 밤이라서 졸렸는지 무척 기본적인 개념인데도 헷갈리더라..

이건 temp 변수에 전혀 새로운 값의 주소를 할당하는 것이므로 test 변수에는 영향을 미치지 않는다.

temp = [ ]  

print(test)    # ['d','b','c]

print(temp)  # [ ]

파이썬 코드

 
def solve(farm, tomatos, tcount, nycount):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    changed = True
    changed_count = 0
    while changed:
        next_tomatos = []
        changed_count += 1
        changed = False
        while tomatos:
            tomato = tomatos.pop()
            x, y = tomato
            for i in range(4):
                temp_x = x + dx[i]
                temp_y = y + dy[i]
                if temp_x < 0 or temp_y < 0 or temp_x >= n or temp_y >= m:
                    continue
                value = farm[temp_x][temp_y]
                # 토마토를 익힌다
                if value == 0:
                    changed = True
                    nycount -= 1
                    # 모든 토마토가 익은 경우
                    if nycount == 0:
                        return changed_count
 
                    farm[temp_x][temp_y] = 1
                    # 다음에 체크할 토마토들
                    next_tomatos.append((temp_x, temp_y))
        tomatos = next_tomatos
    return -1
 
if __name__ == "__main__":
    m, n = map(int, input().strip().split())
    lines = []
    tomato = []
    tomato_count = 0
    notyet_count = 0
    empty_count = 0
    for i in range(n):
        line = list(map(int, input().strip().split()))
        lines.append(line)
 
    for i in range(n):
        for j in range(m):
            value = lines[i][j]
            if value == 0:
                notyet_count += 1
            elif value == 1:
                tomato_count += 1
                tomato.append((i, j))
            elif value == -1:
                empty_count += 1
 
    if tomato_count == 0:
        print(-1)
    elif (tomato_count + empty_count) == (n*m):
        print(0)
    else:
        print(solve(lines, tomato, tomato_count, notyet_count))