백준 7576 토마토 알고리즘 문제 자바 JAVA CODE

 

 

백준 7576 토마토 문제는 토마토가 들어있는 1의 칸에서 시작해서 전체 토마토가 익어가는 기간을 구하는 문제다. 복잡해보이지만 결국 BFS 알고리즘으로 해결할 수 있는 문제다. 첫번째 노드에서 상하좌우로 접하고 있는 노드를 찾아서 counter를 통해 1씩 증가해가면서 마지막 노드까지 가는 최단거리를 구하는 문제와 일맥상통하다.

 

 

 

 

DFS + BFS 알고리즘 이해하기

 

백준 1012 유기농 배추 알고리즘 자바 JAVA

 

백준 2178 미로 탐색 알고리즘 자바 JAVA 풀이

 

 

백준 7576 토마토 문제에서 주의할 점은 토마토가 들어있지 않은 칸에 대한 처리다. 토마토 판 중에 토마토가 들어있지 않으면 counter 2차 배열을 -1로 셋팅해줘야 한다.

 

전체 카운터를 계산한 후에 토마토가 들어있지 않은 칸을 넘어갈 수 없어서 0으로 남아있으면 -1을 리턴하게 된다. 전체 토마토가 익으면 마지막 노드까지 가기 위한 최단거리를 출력하면 된다. 입력 5번은 1번째 노드에서 모두 1로 셋팅이 되기 때문에 0일이 걸린다는 결과값이 나온다.

 

출력값을 리턴하기 위해서는 main 함수가 아닌 bfs 함수에서 리턴값을 받아내야 한다. counter 2차 배열에서 max 값을 구하는 로직이 필요하고, 만약 0이 포함되어 있으면 -1를 리턴하고 빠져나오는 로직이 필요하다.

 

 

 

 

백준 7576 토마토 알고리즘 문제

 

백준 7576 토마토 알고리즘 문제

백준 7576 토마토 알고리즘 문제

백준 7576 토마토 알고리즘 문제

 

 

 

백준 7576 토마토 알고리즘 문제 풀이

익은 토마토가 어디에 들어갈지는 입력값을 받아봐야 한다. 따라서 입력값 중 1을 찾아서 먼저 큐 자료구조에 넣어놓는다. 만약 -1(토마토가 들어있지 않은 빈 칸)을 찾게 되면 counter[][]에 -1을 미리 셋팅 해놓는다. 

 

bfs() 함수는 int 값을 반환하는 함수다. 상하좌우로 좌표를 이동하면서 자식노드를 찾게 되고, 이동한 값을 counter[][]에 차곡차곡 저장하게 된다. 큐의 모든 요소가 poll() 되면 마지막으로 counter[][]내의 max값을 찾게 되고, 만약 0이 들어있으면(토마토가 익지 않으면) -1을 리턴하고 아니면 max 값을 리턴한다.

 

 

 

백준 7576 토마토 알고리즘 문제 자바 JAVA CODE

/*
    Owner : Developer Blog
    Title : 백준 7576 토마토 알고리즘 문제
    Algorithm : BFS 알고리즘
    Date : 2022-03-10
*/

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.stream.Collector;
import java.awt.Point;


public class A_7576 {
    public static int N,M;
    public static int[][] matrix;
    public static boolean[][] visit;
    public static int[][] counter;
    public static int[] NEW_X = {-1,1,0,0};
    public static int[] NEW_Y = {0,0,-1,1};

    public static Queue<Point> queue ;

    public static int max;

    public static void main(String[] args){
        Scanner in  = new Scanner(System.in);

        M = in.nextInt();
        N = in.nextInt();
        matrix = new int[1000][1000];
        counter = new int[1000][1000];
        visit = new boolean[1000][1000];
        queue = new LinkedList<>();

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                matrix[i][j] = in.nextInt();
            }
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(matrix[i][j] == 1){
                    queue.add(new Point(j,i));
                    counter[i][j]=1;
                }else if(matrix[i][j] == -1){
                    counter[i][j]=-1;
                }
            }
        }
        System.out.println(bfs()); 
    }

    public static int bfs(){
        
        while(!queue.isEmpty()){
            Point temp = queue.poll();

            for(int i=0; i<4; i++){
                int new_x = temp.x+NEW_X[i];
                int new_y = temp.y+NEW_Y[i];
                if(new_x>=0 && new_y>=0 && new_x<M && new_y<N){
                    if(matrix[new_y][new_x]==0 && !visit[new_y][new_x]){
                        counter[new_y][new_x] = counter[temp.y][temp.x]+1;
                        queue.add(new Point(new_x, new_y));
                        visit[new_y][new_x]=true;
                    }
                }

            }
        }
        max = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(max < counter[i][j]){
                    max = counter[i][j];
                }
                if(counter[i][j]==0){
                    return -1;
                }
            }
        }

        return max-1;

            
    }
}

 

 

 

 

제출 결과

 

BFS 알고리즘으로 토마토가 익는 가장 빠른 시간을 구했는데, 시간이 1.752초나 걸렸다. 하지만 맞았습니다! 결과가 나온다. 분명 문제에서는 메모리 256MB와 1초 시간 제한이 있었는데 말이다.