[백준 7576] 토마토 (C++/Python)

C++)

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX_NUM 1002
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
int arr[MAX_NUM][MAX_NUM] = { 0, };
int visited[MAX_NUM][MAX_NUM];


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> m >> n;

	for (int i = 0; i < n; i++)
		fill(visited[i], visited[i] + m, -1);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 1) {
				q.push({ i,j });
				visited[i][j] = 0;
			}
		}
	}

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (arr[nx][ny] == 0 && visited[nx][ny] == -1) {
				visited[nx][ny] = visited[x][y] + 1;
				arr[nx][ny] = 1;
				q.push({ nx,ny });
			}
		}
	}

	int ans = -1;
	bool flag = true;
	for (int i = 0; i < n; i++) {
		if (!flag)
			break;

		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0) {
				ans = -1;
				flag = false;
				break;
			}
			
			ans = max(ans, visited[i][j]);
		}
	}

	cout << ans;

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

m, n = map(int, read().rstrip().split())
arr = [ [0] * m for _ in range(n) ] 
visited = [ [-1] * m for _ in range(n) ]

for i in range(n):
    arr[i] = list(map(int, read().rstrip().split()))

    for j in range(m):
        if arr[i][j] == 1:
            q.append((i,j))
            visited[i][j] = 0

while q:
    x, y = q.popleft()

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        if arr[nx][ny] == 0 and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            arr[nx][ny] = 1
            q.append((nx,ny))
            
flag = False
ans = -1

for i in range(n):
    if flag:
        break
    
    for j in range(m):
        if arr[i][j] == 0:
            flag = True
            ans = -1
            break

        ans = max(ans, visited[i][j])

print(ans)