백준 JAVA 7576번 토마토 리뷰

블로그 이전, 2023. 6. 25. 14:16 에 작성했던 글입니다.

 

7576번: 토마토

접근 방법

다른 블로그를 참고하며 풀었다.

 

'익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다'

->Flood fill 알고리즘을 활용한 문제다. 해당 영역의 주변에 모든 셀을 1로 바꾼다는 점에서 알 수 있었다.

https://joomn11.tistory.com/29 Flood fill 개념 참고 블로그

 

Flood fill 은 dfs/bfs 를 사용해야한다.

'토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.'

->토마토 문제는 최소일수를 구하라고 했으니 bfs 로 구해야한다. 

dfs는 최소일수가 아닐 수 있다.

 

토마토가 익은게 한 곳이 아니라 두 곳 이상이라면 동시에 진행해야하는데 이것은 bfs로 표현할 수 있다.

이 부분에 대해 잘 설명해주신 블로그를 가져왔다.

 

예제 입력 3을 기준으로 더 설명해보자면,
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

초기에 (0,0), (3,5) 가 큐에 들어간다.
(0,0)이 poll()된 후, map[1][0]=map[0][0]+1=2가 되고, (1,0)이 큐에 들어가고
(3,5)가 poll()된 후, map[2][5]=map[3][5]+1=2가 되고, (2,5)이 큐에 들어간다.

현재 큐 상태 (1,0), (2,5)
(1,0)이 poll()된 후, map[2][0]=map[1][0]+1=3가 되고, (2,0)이 큐에 들어가고
(2,5)가 poll()된 후, map[1][5]=map[2][5]+1=3가 되고, (1,5)이 큐에 들어간다.

이런 식으로 반복된다.

 

 (출처: https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-7576%EB%B2%88-%ED%86%A0%EB%A7%88%ED%86%A0-Java-%EC%9E%90%EB%B0%94)

 

따라서 bfs를 이용하면 된다. 

 

BFS 풀이 방법

1.최상단 노드 확인 후 큐에 넣고 방문처리

2.큐에서 노드를 빼고 그 노드와 연결되고 방문하지 않은 노드를 큐에 넣고 방문처리

2번 반복

 

 

주요 코드 설명

1.큐에 익은 토마토들을 일단 다 넣는다. 이후 bfs를 실행하는데 큐에서 하나 꺼내서 인접 노드(안 익은 토마토)를 익은 토마토로 만들고 큐에 다시 넣는다.  큐가 비워질 때까지 이를 계속 반복한다. 보통 dfs, bfs 문제는 visited 배열을 만드는데 이 문제에서는 방문여부를 따로 따지지 않았다.  방문여부를 따지지 않아도 되는 문제이기 때문이라고 생각한다.

2.토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.

->dirX, dirY 배열을 사용해 다음으로 이동할 토마토를 정함

3.bfs 끝난 후 배열을 돌면서 0이 (안익은 토마토) 있으면 -1, 없으면 최댓값을 찾은 후 -1 해준다. -1은 처음 더할 때 1부터 시작해서 그런 것 같다.

나의 풀이

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

class tomato{ //토마토 객체
    int x;
    int y;

    tomato(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main{
    static int[] dirX = {0,0,1,-1};
    static int[] dirY = {1,-1,0,0};
    static Queue<tomato> q = new LinkedList<>();
    static int[][] storage;
    static int N,M;
    public static void main(String[] agrs) 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());

        storage = new int[N][M];
        for (int i = 0; i < N; i++) { //배열 초기화
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                storage[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (storage[i][j] == 1) { //익은 토마토라면
                    q.add(new tomato(i, j)); //토마토 객체 생성해서 큐에 넣음
                }
            }
        } //이 코드를 통해 처음 배열에 있는 익은 토마토들을 다 넣음

        System.out.println(bfs());
        //bfs 함수 끝나면 int형 최소일수를 반환할 것임
    }
        public static int bfs(){
            while(!q.isEmpty()){
                tomato t=q.poll(); //큐 반환해서 t와 객체 연결해줌

                int x = t.x;
                int y = t.y;

                for(int i=0; i<4; i++){
                    int nowx = x+dirX[i];
                    int nowy = y+dirY[i];

                    if(nowx>=0&&nowy>=0&&nowx<N&&nowy<M){
                        if(storage[nowx][nowy]==0){//안익은 토마토라면
                            q.add(new tomato(nowx,nowy)); //큐에 넣음
                            storage[nowx][nowy]=storage[x][y]+1; // 일수 증가

                        }
                    }
                }
            }
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(storage[i][j]==0){
                        return -1; //안익은 토마토 있으면 -1 반환하고 함수 종료
                    }
                }
            }
            int max=-2;
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(storage[i][j]>max){
                        max=storage[i][j];
                    }
                }
            }
            return max-1;
        }
    }