[백준] 7576번 : 토마토 (파이썬)

BFS 문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

(1) 메모리 초과난 코드 (실패)

import sys
from collections import deque
c, r = map(int, sys.stdin.readline().split())
graph = []
visited = [[False] * c for _ in range(r)]
start = deque()
for i in range(r):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)
    for j in range(c):
        if l[j] == 1: start.append((j, i, 0))

    def bfs(queue):
        global c, r, cnt
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y, day = queue.popleft()
            visited[y][x] = True # !!!
            count = day
            for i in range(4):
                nextX = x + dx[i]
                nextY = y + dy[i]

                if nextX >= 0 and nextX < c and nextY >= 0 and nextY < r:
                    if visited[nextY][nextX] == True: continue
                    if graph[nextY][nextX] == -1:
                        visited[nextY][nextX] = True 
                        continue # 갈 수 없음.
                    queue.append((nextX, nextY, count + 1))
        return count

count = bfs(start)
for i in range(r):
    for j in range(c):
        if visited[i][j] == False and graph[i][j] != -1: # 토마토가 모두 익지 못하는 상황
            count = -1
            break
print(count)

 

이 문제는 bfs를 사용하는 문제로, 토마토가 모두 익는데까지 걸리는 일수를 구해야 한다. 시작은 익은 토마토(1)에서 부터 해야하는데, 처음 bfs 탐색을 시작할 때 익은 토마토가 여러개 있을 수도 있다. 따라서, 토마토가 익는데 걸리는 일수를 잘 관리하기 위해 queue에 토마토의 x, y좌표 뿐만 아니라 현재 좌표의 토마토가 익는데까지 걸린 일수 또한 같이 queue에 넣어주었다.

 

bfs탐색을 모두 마친 뒤 기존 그래프의 좌표가 -1(갈 수 없는 경로)이 아닌데 방문하지 않은 좌표가 있다면 -1을  출력해야한다. 나는 이를 위해 bfs 탐색을 마친 뒤 이중 for문을 통해 visited 배열에서 False값이 있는지 확인하는 로직을 넣었다. 뭔가 이중 for문 돌리는게 비효율적인거 같아 bfs 탐색할 때 토마토 좌표값이 -1이 아닌데 방문 안한 좌표가 있는지 확인하는 로직을 함께 짜고 싶었지만 어떻게 짜야할지 생각이 나지 않아 그냥 이렇게 짰다.

 

하지만, 위의 코드를 제출하니까 1%대에서 메모리초과가 났다..

 

그 이유는 visited = True해주는 부분을 queue에서 값을 뺄 때 넣어주었기 때문이다. 초기에 queue에 들어가는 값을 방문처리하기 위해 이 로직을 queue에서 값을 뺄 때 넣었던 건데 이 한끝 차이로 메모리초과가 날지는 몰랐다..

따라서, 이 방문처리하는 로직을 queue에서 값을 뺄 때뿐만 아니라 queue에 값을 넣을 때도 추가해주었다. (queue에 값을 넣을 때에만 방문처리를 하면 틀리는 예시가 존재)

 

(2) 수정한 내 코드 (성공)

import sys
from collections import deque
c, r = map(int, sys.stdin.readline().split())
graph = []
visited = [[False] * c for _ in range(r)]
start = deque()
for i in range(r):
    l = list(map(int, sys.stdin.readline().split()))
    graph.append(l)
    for j in range(c):
        if l[j] == 1: start.append((j, i, 0))

    def bfs(queue):
        global c, r, cnt
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            # print(queue)
            x, y, day = queue.popleft()
            visited[y][x] = True
            count = day
            for i in range(4):
                nextX = x + dx[i]
                nextY = y + dy[i]

                if nextX >= 0 and nextX < c and nextY >= 0 and nextY < r:
                    if visited[nextY][nextX] == True: continue
                    if graph[nextY][nextX] == -1:
                        visited[nextY][nextX] = True 
                        continue # 갈 수 없음.
                    # if (nextX,nextY,day) in queue: break 시간초과
                    queue.append((nextX, nextY, count + 1))
                    visited[nextY][nextX] = True 
        return count
if len(start) == r*c:
    count = 0
elif len(start) != 0:
    count = bfs(start)
    for i in range(r):
        for j in range(c):
            if visited[i][j] == False and graph[i][j] != -1: # 토마토가 모두 익지 못하는 상황
                count = -1
                break
else:
    count = -1
# print(visited)
print(count)

     

1) 방문처리하는 로직을 queue에 값을 뺄 때 / 넣을 때 둘다 추가해주었다. 

2) 또, 아래의 반례에 해당하는 예외처리를 해주었다.

▪︎ 처음에 그래프에 익은 토마토(1)가 없을 때 -> bfs를 호출하면 안됨, 바로 -1 출력 (처음에 이 예외처리를 안해줬다가 91%에서 런타임에러남)

2 2

0 -1

-1 0

▪︎  처음에 그래프에 익은 토마토(1) 밖에 없을 때 -> bfs를 호출하면 안됨, 0 출력

2 2

1 1

1 1

▪︎  추가로 생각해봤던 예외 (방문처리하는 로직을 queue에 값을 뺄 때 / 넣을 때 둘다 추가해줬으므로 따로 예외처리 필요 X)

4 1

1 0 0 1

 

if len(start) != 0:
    count = bfs(start)
elif len(start) == r*c:
    count = 0
else:
    count = -1
for i in range(r):
    for j in range(c):
        if visited[i][j] == False and graph[i][j] != -1: # 토마토가 모두 익지 못하는 상황
            count = -1
            break

 

하지만, 예외처리하는 로직을 처음에 이렇게 짰더니 자꾸 95%대에서 틀렸다 ㅠㅠ

그 이유는 처음에 그래프에 익은 토마토(1) 밖에 없을 때 바로 count = 0으로 만들어주고, bfs를 호출하면 안되는데 if문 순서에 의해 bfs를 호출하는 로직이 먼저 실행돼 1이 출력된 것이다.

따라서, if문 순서를 바꾸고, 이중 for문을 돌며 방문 안한 좌표가 있는지 확인하는 로직 또한 if문 안에 넣어줌으로써 이러한 문제를 해결할 수 있었다.

 

느낀점 : 예외처리하는 능력을 기르자 .. ^^