[백준] [Python] #7576 토마토

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

7576번: 토마토

 

3차원 토마토 문제를 보다가 2차원 토마토 문제를 먼저 풀기로 했다.

다른 node에 영향을 주는 노가다 문제니 DFS 혹은 BFS인데, 최소라는 단어가 나오면 일단 BFS로 가라 했다.

 

그래서 아래와 같이 풀었는데, 음 찬찬히 다시보니 문제가 굉장히 많은 코드이지만 가장 큰 문제가 2가지 정도 있다. 

import sys
from collections import deque
sys.stdin = open("input.txt", "r")

m, n = map(int, input().split())
graph = [ list(map(int, input().split())) for _ in range(n)]

def bfs(graph, i, j, cnt):
    direction = [[0,1],[0,-1],[1,0],[-1,0]] #상하좌우
    queue = deque([[i,j]])
    while queue:
        cnt += 1
        v = queue.pop()
        for d in direction:
            if v[0]+d[0]<0 or v[0]+d[0]>=n or v[1]+d[1]<0 or v[1]+d[1]>=m :
                continue
            elif graph[v[0]+d[0]][v[1]+d[1]] == 0:
                graph[v[0]+d[0]][v[1]+d[1]] = 1
                queue.append([v[0]+d[0],v[1]+d[1]])
            elif graph[v[0]+d[0]][v[1]+d[1]] == -1:
                queue.append([v[0]+d[0],v[1]+d[1]])
    return graph

cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1: #돌리면서 토마토를 익힘
            graph = bfs(graph, i, j, cnt)

#다돌았는데 안익은게 있으면 return -1
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            print(-1)
            exit(0)
print(cnt)

1. 방향 메트릭스를 선언하고 dx, dy이런 식으로 변수를 정리하면 더욱 깔끔하게 볼 수 있다.

2. queue..사용법을...모른다...

맞은 버전

import sys
from collections import deque
sys.stdin = open("input.txt", "r")

m, n = map(int, input().split())
graph = [ list(map(int, input().split())) for _ in range(n)]

direction = [[0,1],[0,-1],[1,0],[-1,0]] #상하좌우
ans = 0
queue = deque([])

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1: 
            queue.append([i,j])

def bfs():
    while queue:
        v = queue.popleft()
        for d in direction:
            nx = v[0]+d[0]
            ny = v[1]+d[1]
            if 0<=nx<n and 0<=ny<m and graph[nx][ny] == 0:
                graph[nx][ny] = graph[v[0]][v[1]]+1
                queue.append([nx,ny])

bfs() #돌리면서 토마토를 익힘

#다돌았는데 안익은게 있으면 return -1
for row in graph:
    for j in row:
        if j == 0:
            print(-1)
            exit(0)
    ans = max(ans, max(row))

print(ans-1)

---

참고 https://jae04099.tistory.com/233