7576: 토마토

 

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

 

 

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

import sys
from collections import defaultdict, deque
import itertools

M, N = map(int, sys.stdin.readline().split())
MAP = [[2 for _ in range(M+2)] for _ in range(N+2)]

red_tomatos = []
empty = []
for n in range(1, N+1) :
    MAP[n][1:M+1] = list(map(int, sys.stdin.readline().split()))
    for m, tomato in enumerate(MAP[n][1:M+1]) :
        if tomato == 1 :
            red_tomatos.append((n, m+1))
        elif tomato == -1 :
            empty.append((n, m+1))

# graph
dx = [0, 0, -1, 1] # 상 하 좌 우
dy = [-1, 1, 0, 0]
graph = defaultdict(list)
for n in range(1, N+1) :
    for m in range(1, M+1) :
        if MAP[n][m] == 0 or MAP[n][m] == 1 :
            for d in range(4) :
                new_n = n + dx[d]
                new_m = m + dy[d]
                if MAP[new_n][new_m] == 0 or MAP[new_n][new_m] == 1 :
                    graph[(n, m)].append((new_n, new_m))

visited = [[-1 for _ in range(M)] for _ in range(N)]

def BFS(start, graph, visited) :
    ans = 0
    q = deque([])
    for s in start :
        visited[s[0]-1][s[1]-1] = 0
        q.append((s, 0))
    
    while q :
        u = q.popleft()
        for v in graph[u[0]] :
            if visited[v[0]-1][v[1]-1] == -1 :
                q.append((v, u[1] + 1))
                visited[v[0]-1][v[1]-1] = u[1]+1
                if ans < u[1] + 1 :
                    ans = u[1] + 1
    
    for e in empty :
        visited[e[0]-1][e[1]-1] = 0
    
    if -1 in list(itertools.chain.from_iterable(visited)) :
        print(-1)
    else :
        print(ans)    

BFS(red_tomatos, graph, visited)

아이디어

1. MAP 초기화는 2로 해둔다. 1, 0, -1의 정보를 모두 저장해야 하기 때문!

   추가로 red_tomatos와 empty라는 빈 리스트를 생성하여 BFS 시작점과 visited 수정할 좌표를 미리 저장해둔다.

M, N = map(int, sys.stdin.readline().split())
MAP = [[2 for _ in range(M+2)] for _ in range(N+2)]

red_tomatos = []
empty = []
for n in range(1, N+1) :
    MAP[n][1:M+1] = list(map(int, sys.stdin.readline().split()))
    for m, tomato in enumerate(MAP[n][1:M+1]) :
        if tomato == 1 :
            red_tomatos.append((n, m+1))
        elif tomato == -1 :
            empty.append((n, m+1))

 

2. 그래프 생성 : 비어있지(-1) 않은 경우 graph 노드를 생성한다.

# graph
dx = [0, 0, -1, 1] # 상 하 좌 우
dy = [-1, 1, 0, 0]
graph = defaultdict(list)
for n in range(1, N+1) :
    for m in range(1, M+1) :
        if MAP[n][m] == 0 or MAP[n][m] == 1 :
            for d in range(4) :
                new_n = n + dx[d]
                new_m = m + dy[d]
                if MAP[new_n][new_m] == 0 or MAP[new_n][new_m] == 1 :
                    graph[(n, m)].append((new_n, new_m))

 

3. visited는 -1로 설정한다.

visited = [[-1 for _ in range(M)] for _ in range(N)]

 

4. q의 요소에 좌표 뿐만 아니라 토마토가 익기까지 걸린 시간을 함께 표시한다. ex) ((4, 6), 1)

   그리고 BFS를 탐색하게 되었을 때(v), 기존 노드 u의 시간에 1을 더해 시간 정보를 표시한다.

   방문 여부에도 걸린 시간으로 저장한다.

 

   정답을 구할 때, 처음에 만들어 두었던 empty 요소에 상응하는 visited를 0으로 만들어준다.

   이후 itertools를 활용하여 이중 list를 flatten하고 익지 않은(-1) 부분이 있는지 확인한다.

def BFS(start, graph, visited) :
    ans = 0
    q = deque([])
    for s in start :
        visited[s[0]-1][s[1]-1] = 0
        q.append((s, 0))
    
    while q :
        u = q.popleft()
        for v in graph[u[0]] :
            if visited[v[0]-1][v[1]-1] == -1 :
                q.append((v, u[1] + 1))
                visited[v[0]-1][v[1]-1] = u[1]+1
                if ans < u[1] + 1 :
                    ans = u[1] + 1
    
    for e in empty :
        visited[e[0]-1][e[1]-1] = 0
    
    if -1 in list(itertools.chain.from_iterable(visited)) :
        print(-1)
    else :
        print(ans)    

BFS(red_tomatos, graph, visited)