[Boj/백준] 7576 Python

문제출처:https://www.acmicpc.net/problem/7576

7576번: 토마토

 

1. 문제 접근 방식

1인 원소를 모두 찾아 리스트에 담고

bfs를 돌린다

이때 중요한게 리스트에 담은 원소들을 모두 큐에 넣고 시작한다(1이 두개 이상일 때를 고려해서)

0인 원소를 만날 때마다 값을 1씩 증가시켜준다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(arr):
    queue = deque()
    for i in arr:
        queue.append((i[0],i[1]))

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx < 0 or ny < 0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))

m,n = map(int,sys.stdin.readline().split())
graph = []

for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))
 
start = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            start.append((i,j))

bfs(start)
flag = False
for i in graph:
    if 0 in i:
        flag = True


if flag == True:
    print(-1)
else:
    print(max(map(max,graph))-1)

 

 

3. 결과 및 느낀점

중요한 실수를 했는데 2차원 리스트에서 최대값인 원소 1개를 구하려면

max(max(graph)) 꼴로 하면 안되고 max(map(max,graph))꼴로 구해야 한다.