[백준 java] 7576 - 토마토

7576번: 토마토

---

분명 이전에 토마토 문제를 풀었는데 아직 안푼문제라고 적혀있길래

이전에 푼 문제들을 찾아봤더니

7569-토마토

이전에 푼 문제는 7569 토마토 문제였다. (같은 문제인줄 알았는데 아니더라)

이왕 문제를 본 김에 풀어보기로 했고 이전에 푼 문제보다 더 쉬워서 금방 풀었는것 같다

 

 

문제풀이

입력과 동시에 익은 토마토가 들어오면 바로 큐에 넣어준다 (익은 토마토는 여러개일수 있다)

큐에는 임의의 노드클래스를 생성해 행, 열, 현재날짜 정보를 넣어준다.

큐에 익은 토마토 노드를 다 넣었다면

 

moveTomato에서 큐가 다 빌때까지 상하좌우로 이동을 한다.

(상 하 좌 우 값을 더해 다음 가야할 노드정보를 구한다)

만약 다음에 가야하는 노드의 토마토 상태가 -1이거나 1이면 continue

만약 해당 노드가 이미 방문한 노드라면 continue

혹은 다음 노드 정보가 범위를 벗어난다면 다 continue로 뛰어넘는다.

 

익혀야하는 토마토를 발견하면 해당 토마토를 익히고 day를 증가시킨다

그리고 day의 최대값을 따로 저장한다. (전체를 수행 후 day를 가져와야해서)

 

토마토 익히기가 끝나고 토마토 판의 상태를 확인한다.

만약 덜익은 토마토가 하나라도 있으면 -1을 출력

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B7576 {
    static int N,M;
    static int[][] Board;
    static int[][] D = {{0,-1} , {0,1} , {-1,0} , {1,0}}; //상하좌우
    static Queue<Node> queue = new LinkedList<>();
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        Board = new int[M][N];
        visited = new boolean[M][N];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < N; j++) {
                Board[i][j] = Integer.parseInt(st.nextToken());
                if(Board[i][j]==1) queue.add(new Node(i,j,0));
            }
        }
        moveTomato();
    }

    private static void moveTomato() {
        int res = 0;
        while(!queue.isEmpty()){
            Node temp = queue.remove();
            
            // 최대값 저장 : 전체를 수행 후 day를 저장한다
            if(res<temp.day) res = temp.day;

            for (int i = 0; i < 4; i++) {
                int nr = temp.row + D[i][0];
                int nc = temp.col + D[i][1];

		//해당 토마토가 익힐수 있는 토마토인지 확인하는 if문
                if(nr < 0 || nc < 0 || nr >= M || nc >= N) continue;
                if(visited[nr][nc]) continue;
                if(Board[nr][nc]==-1) continue;
                if(Board[nr][nc]==1) continue;

		//익힐수 있는 토마토라면?
                visited[nr][nc] = true;
                Board[nr][nc] = 1;
                queue.add(new Node(nr,nc, temp.day+1));
            }
        }

	//덜익은 토마토가 있는지 확인
        boolean isRipe = true;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (Board[i][j] == 0) {
                    isRipe = false;
                    break;
                }
            }
        }
        if(isRipe) System.out.println(res);
        else System.out.println(-1);
    }

    static class Node{
        int row,col,day;
        Node(int r, int c, int d){
            row = r;
            col = c;
            day = d;
        }
    }
}

 

한번에 성공!