[ 백준 ] 7576번 : 토마토 - (c++/c, java/자바, python/파이썬)

• 문제

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

7576번: 토마토

---

• 알고리즘 ( 접근 )

bfs 알고리즘을 통해 이미 익은 토마토의 상하좌우 방향을 탐색하고 익지 않은 토마토가 있는 좌표라면  현재 좌표를 익은 토마토로 바꿔준다.

bfs 알고리즘이 끝난 후 익지 않은 토마토가 하나라도 존재한다면 -1을 출력한다.

---

• 풀이 - C++ ( C )

#include <stdio.h>
#include <queue>
#define MAX 1000

using namespace std;

int dX[4] = {-1, 1, 0, 0}; // 상 하 좌 우
int dY[4] = { 0, 0, -1, 1};

int main()
{
    int tomato[MAX][MAX] = { 0 };
    int visit[MAX][MAX] = { 0 };
    int m,n,i,j;
    int cnt = 0,ans = 1;
    int x,y,X,Y;
    queue<pair<pair<int,int>,int>> Q;

    scanf("%d %d", &m, &n);

    for(i=0;i<n;i++)
    {
         for(j=0;j<m;j++)
         {
            scanf("%d", &tomato[i][j]);
            if(tomato[i][j] == 1)
            {
                Q.push({{i,j},cnt});
            }
         }
    }


    while(!Q.empty())
    {
        x = Q.front().first.first;
        y = Q.front().first.second;
        cnt = Q.front().second;
        Q.pop();

        for(i=0;i<4;i++)
        {
            X = x + dX[i];
            Y = y + dY[i];

            if(X < n && Y < m && X >= 0 & Y >= 0 && visit[X][Y] == 0)
            {
                if(tomato[X][Y] == 0)
                {
                    Q.push({{X,Y},cnt+1});
                    visit[X][Y] = 1;
                    tomato[X][Y] = 1;
                }
            }
        }
    }

    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(tomato[i][j] == 0)
            {
                printf("-1");
                return 0;
            }
        }
    }

    printf("%d", cnt);
    return 0;
}

• 풀이 - JAVA

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

class node {
	int x;
	int y;
	
	node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] tomato;
	static Queue<node> Q;
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		
		tomato = new int[n][m];
		Q = new LinkedList<node>();
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				tomato[i][j] = sc.nextInt();
				if(tomato[i][j] == 1) Q.add(new node(i,j));
			}
		}
		
		while(!Q.isEmpty())
		{
			node now = Q.remove();
			int x = now.x;
			int y = now.y;
			
			for(int i = 0; i < 4; i++)
			{
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
					if(tomato[nx][ny] == 0) {
						Q.add(new node(nx,ny));
						tomato[nx][ny] = tomato[x][y] + 1;
					}
				}
			}
		}
		
		int ans = -12345678;
		
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				if(tomato[i][j] == 0) 
				{
					System.out.print("-1");
					System.exit(0);
				}
				ans = Math.max(ans, tomato[i][j]);
			}
		}
		
		System.out.print(ans-1);
	}
}

• 풀이 - PYTHON

from collections import deque
from logging.handlers import QueueListener
m,n = map(int, input().split())
tomato = []
Q = deque([])
dx = [1,-1,0,0]
dy = [0,0,1,-1]

for i in range(n):
    tomato.append(list(map(int,input().split())))
    for j in range(m):
        if tomato[i][j] == 1:
            Q.append([i,j])

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

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

        if 0 <= nx <n and 0 <= ny < m and tomato[nx][ny] == 0:
            Q.append([nx,ny])
            tomato[nx][ny] = tomato[x][y] + 1

result = 0
for i in range(n):
    for j in range(m):
        if tomato[i][j] == 0:
            print(-1)
            exit(0)
        result = max(result, tomato[i][j])
print(result-1)