백준 7576번 - 토마토 (골드 5)

해결방법

 

1. box에 토마토 입력받은 거 넣으면서 

visited에 토마토 상태 기록 - 익은 것: 1, 안 익은 것: 0, 없는 것: -1

 

2. 익은건 큐에 넣기

 

3. bfs 방법을 사용하여 상하좌우 살피기

-> visited가 0인걸 발견하면 전 좌표의 visited값+1 기록, 큐에 담기

 

4. visited가 0인 게 있다면 -1 출력

처음부터 다 익었다면 max=1

아니라면 max-1 출력 (처음값이 1이었기 때문에)

 

 

bfs로 풀기 딱 좋은 문제

: 최소 시간을 구하는 거기 때문에, 상하좌우로 확인해야 하기 때문에

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

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(
                new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(
                new OutputStreamWriter(System.out));

        String[] str=br.readLine().split(" ");
        int M=Integer.parseInt(str[0]); //상자의 가로칸의 수
        int N=Integer.parseInt(str[1]); //상자의 세로칸의 수

        int[][] box=new int[N][M];
        int[][] visited=new int[N][M]; //익는 날짜를 저장하는 배열
        Queue<int[]> q=new LinkedList<>();

        for(int i=0;i<N;i++){
            str=br.readLine().split(" ");
            for(int j=0;j<M;j++){
                box[i][j]=Integer.parseInt(str[j]);
                if (box[i][j] == 1) { //익은 건 큐에 담기
                    q.add(new int[]{i, j});
                    visited[i][j] = 1; // 익은 토마토는 1로 초기화
                } else if (box[i][j] == -1) {
                    visited[i][j] = -1; // 토마토가 없는 칸은 -1로 초기화
                }
            }
        }




        int[] dx={0,0,-1,1}; //상하좌우 x축
        int[] dy={-1,1,0,0}; //상하좌우 y축

        //bfs 탐색
        while(!q.isEmpty()) {
            int[] temp = q.remove();
            int x = temp[0]; //큐에서 꺼낸 x좌표
            int y = temp[1]; //큐에서 꺼낸 y좌표

            for (int i = 0; i < 4; i++) {
                //상하좌우 탐색
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M) { //상자 범위 체크
                    if (visited[nx][ny] == 0) { //익지 않은 토마토이면
                        q.add(new int[]{nx, ny}); //큐에 담고 
                        visited[nx][ny] = visited[x][y] + 1; //날짜 +1일 추가
                    }
                }
            }
        }



        int max=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(visited[i][j]==0){ //안익은게 있다면 -1 출력
                    bw.write("-1");
                    bw.flush();
                    bw.close();
                    return;
                }
                max=Math.max(max,visited[i][j]); 
            }
        }
        if (max == 1) { // 모든 토마토가 처음부터 익어있다면 최대값은 1이 될 수 밖에 없음
            bw.write("0");
        } else {
            bw.write(String.valueOf(max - 1)); // 최댓값에서 1을 빼면 최소 일수가 됨
        }
        bw.flush();
        bw.close();
    }
}

 

 

 

* remove()를 사용하지 않고 poll()을 사용하는 이유

: 

이 코드에서 remove()가 아닌 poll()을 사용하는 이유는 성능상의 이점 때문입니다.

Queue 인터페이스의 remove() 메서드는 큐의 head 원소를 제거하고 그 값을 반환합니다. 하지만 만약 큐가 비어있는 상태에서 remove()를 호출하면 NoSuchElementException이 발생합니다.

반면에 poll() 메서드는 큐의 head 원소를 제거하고 그 값을 반환하지만, 큐가 비어있는 경우에는 null을 반환합니다. 따라서 poll()은 예외 처리가 필요 없어 코드가 더 간결해지고 성능도 향상됩니다.

또한 LinkedList의 경우, remove() 메서드는 원소를 제거할 때마다 배열을 재배열해야 하기 때문에 시간 복잡도가 O(n)이 됩니다. 그러나 poll()은 단순히 head 포인터만 이동시키면 되므로 시간 복잡도가 O(1)이 됩니다.

그렇기 때문에 큐 자료구조를 사용할 때는 poll() 메서드를 사용하는 것이 더 효율적이며, 예외 처리도 더 간단해집니다.