[ BOJ / 파이썬 ] 7576 토마토

/  풀이 1  /

from collections import deque

m, n = map(int, input().split())
tomatoes = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ripped = [[False] * m for _ in range(n)]
q = deque([])
day = 0

def bfs(q):
  new_q = deque([])
  while q:
    x, y = q.pop()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m and ripped == False and tomatoes[nx][ny] != -1:
        ripped[nx][ny] = True
        new_q.append((nx, ny))
      
        
  return new_q

def checkAllRipped():
  global q
  allRipped = True
  for x in range(n):
    for y in range(m):
      if tomatoes[x][y] == 1 and ripped[x][y] == False:
        q.append((x, y))
      elif tomatoes[x][y] == 0:
        allRipped = False
  if allRipped:
    return day
  else:
    global day
    day += 1
    q = bfs(q)
    if q: 
      checkAllRipped()
    else:
      return -1

변수 중첩관계를 해결 못 해서 망해버린 코드입니다.

풀이 보고 다시 정리하겠습니다.

 

아하... 아예 접근이 잘 못 되었었습니다.

 

 

 

/ 제출 2  /

from collections import deque

m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ripped = [[False] * m for _ in range(n)]
q = deque([])
for x in range(n):
  for y in range(m):
    if tomato[x][y] == 1:
      q.append((x,y))
      
def bfs():
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m and ripped[nx][ny] == False and tomato[nx][ny] != -1:
        ripped[nx][ny] = True
        tomato[nx][ny] = tomato[x][y] + 1
        q.append((nx, ny))
        
allRipped = True
day = 0
bfs()
for x in range(n):
  for y in range(m):
    if tomato[x][y] == 0:
      allRipped = False
    day = max(day, tomato[x][y])
if allRipped:
  print(day-1)
else:
  print(-1)

 

다시 풀었는데, 로직 맞는 듯 한데 틀렸다고 나옵니다. 왜? 

 

자고 일어나니 왜인지 바로 보입니다.

tomato가 처음에 1, 0, -1 만 있습니다.

1인 경우는 초기 이중 for문에서 이미 골라냅니다.

그 다음은 0인 경우만 방문 처리를 해야하는데, -1이 아닌 경우라고 제시해서 1인 경우가 섞여들어가게 된 것이었습니다.

이를 토대로 해당 부분을 변경했습니다.

 

 

 

 

/  제출 3  /

from collections import deque

m, n = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

ripped = [[False] * m for _ in range(n)]
q = deque([])
for x in range(n):
  for y in range(m):
    if tomato[x][y] == 1:
      q.append((x,y))
      
def bfs():
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m and ripped[nx][ny] == False and tomato[nx][ny] == 0:
        ripped[nx][ny] = True
        tomato[nx][ny] = tomato[x][y] + 1
        q.append((nx, ny))
        
allRipped = True
day = 0
bfs()
for x in range(n):
  for y in range(m):
    if tomato[x][y] == 0:
      allRipped = False
    day = max(day, tomato[x][y])
if allRipped:
  print(day-1)
else:
  print(-1)