[백준/JAVA] 7576번: 토마토

🔺 문제

7576번: 토마토

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int M,N;
    static int[][] map;
    
    static Queue<int[]> queue = new LinkedList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        M = Integer.parseInt(st.nextToken());   // 가로
        N = Integer.parseInt(st.nextToken());   // 세로
        
        map = new int[N][M];
        
        // 토마토 판 입력
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                // 토마토가 익었다면, 바로 큐에 넣음
                if(map[i][j] == 1) {
                    queue.add(new int[] {i, j});
                }
            }
        }
 
        System.out.println(bfs());
        
    }
    
    private static int bfs() {
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int x = now[0] + dx[d];
                int y = now[1] + dy[d];
                
                if(x < 0 || x >= N || y < 0 || y >= M ) continue;
                
                // 토마토가 안 익었다면, 익은 토마토 추가
                if(map[x][y] == 0) {                    queue.add(new int[] {x, y}); // 인접 노드를 큐에 추가
                    map[x][y] = map[now[0]][now[1]] + 1;  // 🔔 방문 표시 및 최대값 업데이트 🔔 다음 depth = 현재 depth + 1 🔔
                }
            }
            
        }
        
        // 토마토가 모두 익는 최대 날짜 구하기
        int max = Integer.MIN_VALUE;
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 0)    return -1;
                max = Math.max(max, map[i][j]);
            }
        }
        
        if(max == 1) return 0;        // 토마토가 모두 익은 상태인 경우
        else         return max - 1;  // 걸린 일수 = 최대 날짜 - 1
    }
}
 

✅ 해결 아이디어
✔ BFS
- 최대 일수를 구하는 것이므로, 1로 바꾸는 것이 아닌 기존값 + 1을 해 구함 
- 인접 노드에 대한 방문 표시 : 다음 depth = 현재 depth + 1 (이게 계산 겸 방문 표시)

 

 

52번째 줄을 놓쳤다...

방문 표시는 visited 배열 쓰지 말고,

현재 노드 depth 값 + 1로 하는 것으로...

 

 

---

🔺 다른 풀이들

- 날짜 구하는 방식만 아주 조오금 다름

로그인

---

💬 느낀 점

방문 배열 visited[][] 가 필요 없는 이유

그냥 map[][] 배열의 값을 업데이트 하면 되는 것이다,,,,,

map[][] 배열 값이 0이면 방문 안 한 거니까...

 

1회독	2회독	3회독	4회독	5회독
V	230810	240106	240618

 

 

+ 24.01.06 2회독

ArrayDeque을 썼더니 훨씬 빨라졌다.

 

놓친 부분

- 토마토가 저장 초기부터 모두 익은 경우

→ 완전탐색 통해 0을 안 갖고 있을 때의 최댓값을 구해 이 값이 1일 때가 저장 초기부터 모두 익은 상태이므로 0을 출력한다.

 

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    static int M, N;
    static int[][] map;
    
    static Queue<int[]> q = new ArrayDeque<>();
    static int max = Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                if(map[i][j] == 1) {
                    q.add(new int[] {i, j});
                }
            }
        }
        
        bfs();
        
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 0) {    // 토마토가 익지 않은 칸이 있다면, -1 출력하고 종료
                    System.out.println(-1);
                    return;
                }
                max = Math.max(max, map[i][j]);
            }
        }
        
        System.out.println(max == 1 ? 0 : max - 1);
    }
    
    private static void bfs() {
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ;d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(!inRange(nx, ny))    continue;
                
                if(map[nx][ny] == 0) {    // 익지 않은 토마토 익히기
                    map[nx][ny] = map[now[0]][now[1]] + 1;    // 날짜 누적해 계산하는 겸 방문 처리
                    q.add(new int[] {nx, ny});                    
                }
            }
        }        
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}
 

---

(참고)

[백준] 7576번 토마토 - Java, 자바

[백준 알고리즘] 백준 7576번 토마토 자바(Java)

[BOJ] 백준 7576 - 토마토 (자바)