토마토 - 백준(7576, 그래프 탐색)

🎯 단지번호붙이기

토마토 - 7576, 그래프 탐색, 골드5

🧐 알고리즘[접근방법]

1. 토마토 정보가 담긴 배열 map, 일수를 저장하기 위한 배열 dist 선언

2. 토마토가 있는 배열을 Queue에 저장 후 BFS를 통해서 일수 진행

3. map에 모든 칸에 토마토가 있으면 최대 일수 출력, 아니면 -1 출력

👨‍💻 소스

import java.util.*;

public class Main {

  public static class Node {
    int x;
    int y; 
    
    Node(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
  
  public static int N; // 세로
  public static int M; // 가로
  
  public static int[][] map;
  public static int[][] dist;
  
  public static final int[] dx = {0, 0, 1, -1};
  public static final int[] dy = {-1, 1, 0, 0};
  
  public static int day = 0;
  
  /*
   *  익은 토마토 : 1
   *  익지 않은 토마토 : 0
   *  토마토 X : -1
   */
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    M = sc.nextInt();
    N = sc.nextInt();
    sc.nextLine();
    
    map = new int[N][M];
    dist = new int[N][M]; // 일수를 계산하기 위한 배열
    
    Queue<Node> q = new LinkedList<Node>();
    
    for(int i = 0 ; i < N ; i++) {
      for(int j = 0 ; j < M ; j++) {
        map[i][j] = sc.nextInt();
        
        if(map[i][j] == 1) {
          q.add(new Node(i, j));
        }
        
      }
    }
    
    BFS(q);
   
    if(isFull()) {
      System.out.println(day);
    } else {
      System.out.println("-1");
    }
    
    sc.close();
  }
  
  public static int BFS(Queue<Node> q) {
    
    while(!q.isEmpty()) {

      Node n = q.poll();
      
      for(int i = 0 ; i < dx.length ; i++) {
        int x = n.x + dx[i];
        int y = n.y + dy[i];
        
        if(0 <= x && x < N && 0 <= y && y < M) {
          if(map[x][y] == 0 && dist[x][y] == 0) {
            map[x][y] = 1;
            dist[x][y] = dist[n.x][n.y] + 1;
            q.add(new Node(x, y));
            day = Math.max(day, dist[x][y]);
          }
        }
      }
    }
    
    return day;
  }
  
  public static boolean isFull() {
    
    for(int i = 0 ; i < N ; i++) {
      for(int j = 0 ; j < M ; j++) {
        if(map[i][j] == 0) {
          return false;
        }
      }
    }
    
    return true;
  }

}

🏅 결과

📖 관련 지식