백준 7576번 : 토마토 (JAVA) 문제 풀이

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

7576번: 토마토

---

 

✏️ 문제

 

🔐 문제 해결

이 문제는 미로 탐색 문제처럼 풀면 된다. 

대신 이 문제에서 주의해야할 점은 미로 탐색 문제처럼 한곳에서 출발하는게 아니라, 시작점이 여러지점이라는 점이다.

이것 때문에 머리 아팠는데 생각해보면 그리 어렵지 않다.

아래 코드를 보면서 살펴보자.

int[][] days = new int[N][M];
int[][] tomatos = new int[N][M];

// N, M 주의! 우리는 M을 행, N을 열로 사용!
for(int i=0; i<M; i++){
	st = new StringTokenizer(bf.readLine();
	for(int j=0; j<N; j++){
	    int num = Integer.parseInt(st.nextToken());
          tomatos[i][j] = num;
          // 1(익은 토마토)이면 큐에 넣어준다!
          if( num == 1 ){
              qu.offer(new Pair(i, j));
              days[i][j] = 0;
          }else{
              days[i][j] = -1;
          }
    }
}

 

먼저 익은 토마토(1)일때는 큐에 넣어준다! (시작점 세팅).

그리고, 익지 않았으면 days[i][j]에 -1값을 넣어준다. -> 나중에 방문여부를 확인하기 위해서

 

가장 핵심이 되는 코드이다! 

익은 토마토 상,하,좌,우에 익지 않은 토마토가 있다면 토마토를 익은 상태로 바꾸고, 해당 days의 값을 +1해서 넣어준다!!

아래 코드를 살펴보자.

while(!qu.isEmpty()){
    Pair p = qu.poll();
    
    // 상하좌우 순회
    for(int i=0; i<4; i++){
        int nX = p.x + dx[i];
        int nY = p.y + dy[i];
        
        if(nX <0 || nX >= N || nY < 0 || nY >= M){
            continue;
        }
        // 토마토가 없거나, 이미 방문했으면 PASS!
        if(tomatos[nX][nY] == -1 || days[nX][nY] != -1){
            continue;
        }
        // 익은 토마토를 큐에 넣어주고, 안익은 토마토의 개수 -1
        qu.offer(new Pair(nX, nY)); notYet--;
        // 날짜를 +1 하여 넣어줍니다.
        days[nX][nY] = days[p.x][p.y] + 1;
        // 해당 날짜가 최종 날짜인지 구분
        if(result < days[nX][nY]){
            result = days[nX][nY];
        }
    }
}

미리 넣어줬던 익은 토마토를 큐에서 차례대로 꺼내면서, 해당 토마토의 상,하,좌,우를 탐색해서 안익은 토마토가 있다면 큐에 넣어주고, 해당 토마토의 날짜를 자신을 익히게 했던 토마토(?)의 날짜 + 1 한 값을 넣어준다! (말이 이상한데 잘 이해해보자..)

 

🖥 전체 코드

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

public class Main {
    public static void main(String args[]) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(bf.readLine());
      
      int result = 0;      // 최종 날짜
      int notYet = 0;      // 안익은 토마토
      int M = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());
      int[][] days = new int[N][M];     // 날짜를 저장할 2차원배열
      int[][] tomatos = new int[N][M];  // 토마토의 상태를 저장할 2차원배열
      
      Queue<Pair> qu = new LinkedList<>();
      int[] dx = {1, 0 , -1, 0};    // 상하좌우 좌표 계산을 위한 배열
      int[] dy = {0, 1, 0, -1};
      
      
      // 토마토 상태 입력
      for(int i=0; i<N; i++){
          st = new StringTokenizer(bf.readLine());
          for(int j=0; j<M; j++){
              days[i][j] = -1;  // 방문여부를 위해 -1로 초기화
              int num = Integer.parseInt(st.nextToken());
              tomatos[i][j] = num;
              if(num == 1){
                  qu.offer(new Pair(i, j)); // 익은 토마토만 큐에 넣어준다.
                  days[i][j] = 0;           // 해당 날짜 0일으로 세팅
              }else if(num == 0){
                  notYet++;     // 익지 않은 토마토 +1
              }
          }
      }
      
      // 안익은 토마토가 없다면 종료.
      if(notYet == 0){
          System.out.print(0);
          System.exit(0);
      }
      
      // 익은 토마토가 만약 n개 일때, 걸린 날짜 / n 인가?
      while(!qu.isEmpty()){
          Pair p = qu.poll();
          
          // 상하좌우 순회
          for(int i=0; i<4; i++){
              int nX = p.x + dx[i];
              int nY = p.y + dy[i];
              
              if(nX <0 || nX >= N || nY < 0 || nY >= M){
                  continue;
              }
              // 토마토가 없거나, 이미 방문했으면 PASS!
              if(tomatos[nX][nY] == -1 || days[nX][nY] != -1){
                  continue;
              }
              // 익은 토마토를 큐에 넣어주고, 안익은 토마토의 개수 -1
              qu.offer(new Pair(nX, nY)); notYet--;
              // 날짜를 +1 하여 넣어줍니다.
              days[nX][nY] = days[p.x][p.y] + 1;
              // 해당 날짜가 최종 날짜인지 구분
              if(result < days[nX][nY]){
                  result = days[nX][nY];
              }
          }
      }
      
      // 만약 아직도 익지 않은 토마토가 있다면 -1 출력!
      if(notYet > 0){
          System.out.print(-1);
      }else{
          System.out.print(result);
      }
    }
    
    public static class Pair{
        int x, y;
        
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        
        public int getX(){
            return x;
        }
        public int getY(){
            return y;
        }
        public void setX(int x){
            this.x = x;
        }
        public void setY(int y){
            this.y = y;
        }
    }
}