[백준 7576] 토마토

#7576

BFS를 이용하면 되겠다는 생각이 들었다.
방문 배열을 사용해서 미로찾기 문제를 풀 때 처럼 카운트를 하나씩 증가시키면 되겠다고 생각했는데, 미로찾기 문제와 다른 점은 다양한 곳에서 동시에 시작할 수 있다는 점이다.

이 부분은 처음부터 시작점(1인 토마토)를 큐에 다 넣어주느 방식으로 해결했다.

1차 시도 - 시간초과

먼저 방문하면 당연히 카운트가 적을테니 방문 안한 것들만 카운트를 올려주는 방식을 취했다. 하지만 시간초과...!

x,y=map(int,input().split())
matrix=[[0]*x for _ in range(y)]
visit=[[0]*x for _ in range(y)]
direct = [[0,1],[1,0],[-1,0],[0,-1]]
queue =[]

#matrix 만들기
for i in range(y) :
  new=input().split()
  for j in range(x) :
    matrix[i][j] = visit[i][j] = int(new[j])
    if matrix[i][j] == 1 :
      queue.append([i,j])

if len(queue) != 0 : #1인 토마토가 하나도 없으면 BFS 순회 할 필요 없음.
  while queue :
    i = queue[0][0]
    j = queue[0][1]
    queue.pop(0)
    for d in direct :
      di = i + d[0]
      dj = j + d[1]
      if (0<=di<y and 0<=dj<x) and matrix[di][dj]==0:
        visit[di][dj] = visit[i][j] + 1
        matrix[di][dj] = 1 #다시 탐색하지 않기 위해 1로 바꿔줌.
        queue.append([di,dj])

maximum=0
flag=0
for i in range(y) :
  for j in range(x) :
    if visit[i][j] == 0 : 
#bfs를 돌고도 방문하지 않은 부분 = 갈 수 없는 부분 = 모든 토마토를 익힐 수는 없다.
      flag = 1
      break
    elif visit[i][j] > maximum :
      maximum = visit[i][j]
  if flag == 1 : break

if flag == 1 : print(-1)
else : print(maximum-1)

2차시도 - 맞았습니다

틀린 이유를 알았다.
BFS는 큐를 이용한 방식이니까 파이썬의 리스트를 이용해 append로 삽입하고 pop(1)로 삭제해주었는데, pop(1)의 시간복잡도가 무려 O(N)이었다.
그래서 앞에서 pop연산이 필요한 경우 from collections import deque 해서 라이브러리를 이용하는 것이 좋다고 한다.

deque가 list와 비슷하게 쓰이지만 시간 복잡도가 훨씬 줄어든다!

from collections import deque

x,y=map(int,input().split())
matrix=[[0]*x for _ in range(y)]
visit=[[0]*x for _ in range(y)]
direct = [[0,1],[1,0],[-1,0],[0,-1]]
queue = deque()

#matrix 만들기
for i in range(y) :
  new=input().split()
  for j in range(x) :
    matrix[i][j] = visit[i][j] = int(new[j])
    if matrix[i][j] == 1 :
      queue.append([i,j])

cnt=0

#bfs 탐험
if len(queue) != 0 :
  while queue :
    i = queue[0][0]
    j = queue[0][1]
    queue.popleft()
    for d in direct :
      di = i + d[0]
      dj = j + d[1]
      if (0<=di<y and 0<=dj<x) and matrix[di][dj]==0:
        visit[di][dj] = visit[i][j] + 1
        matrix[di][dj] = 1 #다시 탐색하지 않기 위해 1로 바꿔줌.
        queue.append([di,dj])
        cnt = visit[di][dj] #제일 마지막에 넣는 카운트를 출력하기 위한 변수

#토마토가 있지만 방문 할 수 없는 곳이 있는지, 다 방문했다면 얼마나 걸리는지 출력하는 부분
flag=0
for i in range(y) :
  for j in range(x) :
    if visit[i][j] == 0 : #bfs를 돌고도 방문하지 않은 부분 = 갈 수 없는 부분 = 모든 토마토를 익힐 수는 없다.
      flag = 1
      break
  if flag == 1 : break

if flag == 1 : print(-1)
elif cnt == 0 : print(cnt)
else : print(cnt-1)