[백준] 7576. 토마토 / python 파이썬

🚩 그래프탐색, BFS

 

thinking

queue에다 처음 1인 애들의 좌표를 다 넣고 사방탐색하면서 1로 바꾸고, 바꾼 애들의 좌표를 또 큐에 넣고 이런식으로 해결했다.

그리고 경로 길이를 구해야해서 길이체크할 visited를 만들어줬다.

 

  ▶ point 1   

처음부터 모두 1이면 0을 출력, 최종적으로 0이 남아있으면 -1을 출력해야 하는데 이걸 어떻게 해야할까 고민하다
파이썬의 all과 any에 대해 알게됐다. 대박사건

---

all(), any() 함수는 파이썬 빌트인 함수이며 조건 성립 유무에 따라 True / False를 리턴해준다.
인자는 하나만 올 수 있고, 반복가능한 자료형(iterable)이어야한다.
파이썬에서 빈 값, 0, None은 False로 인식한다.

All

조건이 전부 True이면 True를 리턴, 하나라도 틀릴 경우 False를 리턴한다.
(인자로 받은 자료형이 비어있으면 True를 반환한다 - ex. all([ ]) : True )

Any

조건중 하나라도 맞으면 True를 리턴하고, 모든 요소가 False인 경우에만 False를 리턴한다.
(인자로 받은 자료형이 비어있으면 False를 반환한다 - ex. any([ ]) : False  )

#a에 0이 하나도 없으면 True 리턴
if all(0 not in array for array in a):
	return True

#a에 0이 하나라도 있으면 True 리턴
if any(0 in array for array in a):
	return True

 

  ▶ point 2   

---

2차원 배열에서 최대값, 최소값 구하는 법 : map

arr = [[1,2,3],[4,5,6],[7,8,9]]

# 최대값
max(map(max, arr))  # 9 

# 최소값
min(map(min, arr))  # 1 

 

 

코드

from collections import deque

M, N = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

if all(0 not in array for array in a):
    print(0)

else:
    deq = deque()
    for i in range(N):
        for j in range(M):
            if a[i][j] == 1:
                deq.append((i,j))

    while deq:
        x, y = deq.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0<=nx<N and 0<=ny<M and a[nx][ny] == 0:
                a[nx][ny] = 1
                visited[nx][ny] = visited[x][y]+1
                deq.append((nx,ny))

    if any(0 in array for array in a):
        print(-1)
    else:
        print(max(map(max, visited)))