[백준] 7576 토마토 문제 파이썬 풀이

이 글을 쓰는 이유?

반례 찾기가 너무 힘들었던 문제였던 것 같다.
이 링크에서 나오는 반례를 모두 충족하지 못하면 문제가 틀렸다고 나온다.

문제 링크

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

문제 설명은 위에 들어가서 읽는게 더 정확할테니 따로 기술하지 않겠다.

내 첫 풀이

위상정렬에서 사용하던 indegree를 가져와서 아직 익지 않은 토마토를 Tracking해서 풀어주는 방식을 사용했다. 근데 이 코드를 사용하면 1%에서 무조건 실패가 났다. 반례란 반례는 다 찾아보고 테스트 코드도 다 확인했지만 이상한 점은 없었다.

근데 단톡방에서 어떤분이 '모든 토마토가 익는걸 확인하셧나요?'

라고 질문하시기에 graph의 값이 다 1로 변하는지 확인하던 중

    30 19
    0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1
    -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 -1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

이 테스트 케이스의 답은 나오지만 모든 graph에 1이 표시되지 않고 듬성듬성 0이 보이는 것을 확인했다. 조금 머리를 굴려보니 답이 나왔다.
r : 1, c : 11 도 indegree['111']로 저장이 되고 r : 11, c : 1 도 indegree['111']로 저장이 되어서 발생하는 문제다.
저 테스트 케이스에서 어떤 실패가 나는지는 모르겠지만 이것과 연관되있음이 분명해 보였다.

그래야만 한다.

from collections import deque

C, R = map(int, input().split())
graph = []
for _ in range(R):
  graph.append(list(map(int, input().split())))

# 안익은 토마토
indegree = {}
start_q = deque()

for r in range(R) :
  for c in range(C) :
    if graph[r][c] == 0 :
      indegree[f"{r}{c}"] = True
    elif graph[r][c] == 1 :
      start_q.append([r,c])
_d = [[1,0],[-1,0],[0,1],[0,-1]]
indegree_cnt = len(indegree.keys())
if len(graph) <= 0 :
  print(-1)
elif indegree_cnt <= 0 :
  print(0)
else :
  cnt = 0
  while True :
    cnt += 1
    next_q = deque()
    for q in start_q :
      r, c = q
      for d in _d :
        nr, nc = r + d[0], c + d[1]
        if -1 < nr < R and -1 < nc < C :
          if f'{nr}{nc}' in indegree :
            next_q.append([nr,nc])
            indegree_cnt -= 1
            graph[nr][nc] = 1
            del indegree[f'{nr}{nc}']
    # 모든 토마토가 다 익은 경우
    if indegree_cnt == 0 :
      print(cnt)
      break
    elif len(next_q) > 0 :
      start_q = next_q
    # 모든 q를 다 순회했지만 아직 안익은 토마토가 남은 경우
    else :
      print(-1)
      break

내 두 번째 풀이

그냥 f'{r}{c}'와 같은 형식으로 들어가는 모든 라인에 f'{r}-{c}' 처럼 구분자를 넣어서 해결해줬다.

from collections import deque

C, R = map(int, input().split())
graph = []
for _ in range(R):
  graph.append(list(map(int, input().split())))

# 안익은 토마토
indegree = {}
start_q = deque()

for r in range(R) :
  for c in range(C) :
    if graph[r][c] == 0 :
      indegree[f"{r}-{c}"] = True
    elif graph[r][c] == 1 :
      start_q.append([r,c])
_d = [[1,0],[-1,0],[0,1],[0,-1]]
indegree_cnt = len(indegree.keys())
if len(graph) <= 0 :
  print(-1)
elif indegree_cnt <= 0 :
  print(0)
else :
  cnt = 0
  while True :
    cnt += 1
    next_q = deque()
    for q in start_q :
      r, c = q
      for d in _d :
        nr, nc = r + d[0], c + d[1]
        if -1 < nr < R and -1 < nc < C :
          if f'{nr}-{nc}' in indegree :
            next_q.append([nr,nc])
            indegree_cnt -= 1
            graph[nr][nc] = 1
            del indegree[f'{nr}-{nc}']
    # 모든 토마토가 다 익은 경우
    if indegree_cnt == 0 :
      print(cnt)
      break
    elif len(next_q) > 0 :
      start_q = next_q
    # 모든 q를 다 순회했지만 아직 안익은 토마토가 남은 경우
    else :
      print(-1)
      break

좀 더 효율적인 풀이?🤔

너무 파이써닉하게 풀이된 풀이를 안좋아하는데 이 블로그의 풀이가 깔끔해보여서 가져왔다.
내가 한 풀이보다 약 3배 정도 빠르다.

👇 위가 내 풀이 아래가 저 블로그에서 나온 풀이

from collections import deque
import sys
input = sys.stdin.readline

m, n = map(int, input().split()) # 가로, 세로
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 익은 토마토의 위치 queue에 추가
queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append([i, j])

# BFS 함수 정의
def bfs():
    while queue:
        x, y = queue.popleft()
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 상하좌우에 익지 않은 토마토(0)가 있으면 1을 더해 몇 번째인지 세주고
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny)) # 큐에 새로운 토마토 위치 추가

# BFS; 토마토 익히기 시작
bfs()

# bfs 종료 후
day = 0
for row in graph:
    for i in row:
        if i == 0:  # 익지 않은 토마토가 있으면(=토마토가 모두 익지 못하는 상황) -1 출력
            print(-1)
            exit() # 다음 행의 여부와 관계 없이 -1만 출력해야하므로 종료시킴
    else: # 그래프에서 가장 큰 값이 마지막으로 익은 토마토임 → 한 줄씩 최댓값을 day로 갱신하며 최댓값 찾기
        day = max(day, max(row)) 

# 처음 시작을 0이 아닌 1부터 했으므로 -1을 해야 날짜를 구할 수 있음 
print(day-1)