토마토

풀이

 이 문제의 핵심은 BFS의 시작 포인트가 여러개라는 점이다. 만약 시작 위치 1개를 기준으로 BFS를 돌리고, 다시 다른 시작 위치 1개를 기준으로 BFS를 돌리는 방식으로 이 문제에 접근하면 총 시간 복잡도는 O(N²M²)가 되어 시간 초과 판정이 뜬다. 따라서 모든 시작 위치를 큐에 넣고 BFS를 돌려야 한다. 그러면 총 시간 복잡도가 O(NM)이 되어 문제를 풀 수 있다.

시간 복잡도 : O(MN)
💡 Java 풀이입니다. Python 풀이와 다를 수 있습니다.

Java

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static int M, N;

    static List<Point> pointList;

    static int[] dx = {0, 0, 1, -1};

    static int[] dy = {1, -1, 0, 0};

    static class Point{
        int x;
        int y;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static void BFS(){
        Queue<Point> queue = new LinkedList<>();
        for(Point point : pointList){
            queue.add(point);
        }

        while (!queue.isEmpty()){
            Point p = queue.poll();
            for(int i=0; i<4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(0<=nx && nx<N && 0<=ny && ny<M){
                    if(graph[nx][ny]==0) {
                        graph[nx][ny] = graph[p.x][p.y] + 1;
                        queue.offer(new Point(nx, ny));
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        graph = new int[N][M];
        pointList = new ArrayList<>();
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                if(graph[i][j]==1)
                    pointList.add(new Point(i, j));
            }
        }
        BFS();
        int max_value = Integer.MIN_VALUE;
        boolean flag = true;
        for(int i=0; i<N; i++){
            if(flag==false)
                break;
            for(int j=0; j<M; j++){
                if(graph[i][j]==0){
                    bw.write(String.valueOf(-1));
                    flag = false;
                    break;
                }
                max_value = Integer.max(max_value, graph[i][j]);
            }
        }
        if(flag==true) {
            if (max_value == 1)
                bw.write(String.valueOf(0));
            else
                bw.write(String.valueOf(max_value-1));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

Python

from collections import deque
import sys
N, M = map(int, input().split())
graph = []
for i in range(M):
    graph.append(list(map(int, sys.stdin.readline().split())))

queue = deque()
for x in range(M):
    for y in range(N):
        if graph[x][y] == 1:
            queue.append((x,y))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs():
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<M and 0<=ny<N:
                if graph[nx][ny] == 0:
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append((nx,ny))

bfs()
max_value = -10
for x in range(M):
    for y in range(N):
        if graph[x][y] == 0:
            print(-1)
            exit(0)
    max_value = max(max_value, max(graph[x]))
if max_value == 1:
    print(0)
else:
    print(max_value-1)