메모한 것
-
익은 토마토 칸 1 vs 익지 않은 토마토 칸 0 vs 토마토 없는 칸 -1
-
익지 않은 토마토는 주변에 익은 토마토의 영향을 받아 익음 -> DFS BFS
- 이때 인접하다 = 상하좌우 (대각선 x)
-
N x M 행렬 (세로 x 가로)
-
알고싶은 것
- 며칠이 지나야 토마토가 전부 익게 되는지 "최소 일수"
-
이거 BFS 네 => graph에서 1인 것부터 풀스캔하면서 BFS수행하고
- BFS 순회 한 번 끝날 때 cnt += 1 (노드이동x)
-
근데 BFS 맞는데 만약 첫 셋팅에서 1이 여러 개면(=전파시키는 토마토) "병렬"로 수행되어야 할 것 같은데?!
-
그리고 테케 2번 보면 토마토가 모두 익지 못하는 경우(=하나라도 안익은 경우) -1 출력 해야 함
- 따라서 모두 끝난 후에 count(0) > 0 이면, 아니면 0 in graph 이면 answer = -1 바꾸기
찐 BFS 방식 + 최단경로는 BFS (이거 중요)
- 내가 지금까지 한건 시작점이 하나인 경우에만 BFS인데
- 해당 문제는 시작점이 두 개 이상인 경우의 BFS임
- 최단경로 구하기 문제에서도 사용된다고 함
- 시작 토마토 위치를 전부 Queue에 넣어준 후에 BFS를 수행하는 것이다
- 지금까지 공부한 방식은 시작 토마토 위치 하나만 넣어주고
- 걔가 끝나면 걔 주변의 위치를 파악해서 하는 것이었으나
- 시작 위치를 처음부터 que에 넣어주고 que(A, B)
- -> 시작점 A의 이웃 다 넣어준 후 que(B, a, b, c)
- -> A의 이웃인 a의 이웃들을 수행하는게 아니라,
- -> 시작점 B의 이웃 먼저 다 넣어주고 A의 이웃인 a를 수행 que(a, b, c, x, y, z)
- 최단경로 방법
- 방문을 했냐 안했냐 (X)
- 이동할 때마다 값을 갱신 (graph[ny][nx] = graph[prev_y][prev_x] + 1)
''' 내가 푼 - 답아님 - 시작이 하나일 경우 (근데 애초에 답도 안나옴) '''
from collections import deque
def bfs(y, x, graph, n, m, cnt):
cnt += 1
graph[y][x] = 1
que = deque([[y, x]])
# 상 하 좌 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
while que:
tmp = que.popleft()
for i in range(4):
ny = tmp[0] + dy[i]
nx = tmp[1] + dx[i]
if ny < 0 or n <= ny or nx < 0 or m <= nx: continue
if graph[ny][nx] == -1: continue
if graph[ny][nx] == 0:
graph[ny][nx] = 1
que.append([ny, nx])
cnt += 1
return cnt
#m, n = map(int, input().split()) # n = 세로, m = 가로
#graph = [list(map(int, input().split())) for _ in range(n)]
m, n = 6, 4
# test case 1
graph = [[0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1]]
# test case 3
#graph = [[1, -1, 0, 0, 0, 0], [0, -1, 0, 0, 0, 0], [0, 0, 0, 0, -1, 0], [0, 0, 0, 0, -1, 1]]
answer = 0
cnt = 0
for y in range(n):
for x in range(m):
if graph[y][x] == -1: continue
if graph[y][x] == 0:
answer += bfs(y, x, graph, n, m, cnt)
cnt = 0
for small in graph:
for i in range(m):
if small[i] == 0: # 하나라도 있으면
answer = -1
print(answer)
진짜 solution (최단경로 BFS 활용)
''' 블로그 어떻게 했나 참고하고 다시 푼 '''
from collections import deque
import sys
input = sys.stdin.readline
m, n = map(int, input().split()) # n = 세로, m = 가로
graph = [list(map(int, input().split())) for _ in range(n)]
answer = 0
cnt = 0
que = deque()
# 토마토의 위치 전부 push
for y in range(n):
for x in range(m):
if graph[y][x] == 1:
que.append([y, x])
# 상 하 좌 우
dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
while que:
ay, ax = que.popleft()
for i in range(4):
ny, nx = ay + dy[i], ax + dx[i]
if 0 <= ny < n and 0 <= nx < m and graph[ny][nx] == 0:
graph[ny][nx] = graph[ay][ax] + 1 # (핵중요) 최단거리 값 키워나가
que.append([ny, nx])
flag = False
for small_g in graph:
if 0 in small_g: # 하나라도 있으면
flag = True
break
answer = max(answer, max(small_g))
print(-1 if flag else answer - 1)
# => 처음 시작할 때 익은토마토는 1이고, 첫 익은 애의 +1 = 2로 시작했으니까 -1해줘야함
근데 왜 -1이냐면,
=> 처음 시작할 때 익은토마토는 1이고, 첫 익은 애의 +1 = 2로 시작했으니까 -1해줘야함
else: print(answer-1)
Do My Best