[baekjoon] 7576 토마토 골드5

백준 BFS 문제
링크 : https://www.acmicpc.net/problem/7576
시간제한 : 1초
메모리 제한 : 256MB

설명

• 지난 문제에서는 하나씩 증가하면서 증가했지만, 이번에는 양 옆을 감염시키듯이 퍼저나감.

---

코드

from collections import deque

n,m = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(m)]
visited = [[0] *n for _ in range(m)]
cnt = 0
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q = deque()
def BFS(x,y):
    
    q.append((x,y))
    temp = 1
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0<= nx < m and 0<= ny <n and visited[nx][ny] == 0:
                if arr[nx][ny] == 0:
                    
                    arr[nx][ny] = arr[x][y] +1
                    temp = max(arr[nx][ny],temp)
                    visited[nx][ny] = 1
                    q.append((nx,ny))
    return temp -1 
    

for i in range(m):
    for j in range(n):
        if arr[i][j] == 1 and visited[i][j] == 0:
            q.append((i,j))
            

for i in range(m):
    for j in range(n):
        if arr[i][j] == 1 and visited[i][j] == 0:
            cnt = max(BFS(i,j),cnt)


for i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            cnt = -1
            

print(cnt)

• 익은 토마토를 미리 deque에 넣는다는 것만 빼면 이전 문제들과 유사하다.

---

깨달은점

• visited문이 없이도 잘 수행된다는 것을 알았다.
• 아래쪽 코드 for문이 남발되서 채점시간이 오래 걸린 것 같다.
• 아래와 같이 수정할 수 있다.

            
while q:
    x,y = q.popleft()
    for i in range(4):
        nx,ny = x+dx[i],y+dy[i]
        if 0<= nx < m and 0<= ny <n and visited[nx][ny] == 0:
            if arr[nx][ny] == 0:
                arr[nx][ny] = arr[x][y] +1
                visited[nx][ny] = 1
                q.append((nx,ny))
    

  
for i in range(m):
    for j in range(n):
        if arr[i][j] == 0:
            print(-1)
            exit(0)
        cnt = max(arr[i][j],cnt)    

• exit(0)를 하면 프로그램을 종료시키며 아래 코드를 수행하지 않는다는 것을 복기했다.
  +++ 추가
• exit()이나 quit()같은 경우 쉘의 정보까지 없애버리기 때문에 추천하지 않는 방법이라고 되어있다.
• import sys를 해서 sys.exit(0)를 사용하는 것이 좋은 방법이다.