[BFS] - G5_7576_토마토

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

7576번: 토마토

 

토마토 문제는 BFS를 하다보면 가끔 비슷한 유형의 문제들이 나와서 한 번 풀어 봤는데 다시보니까 또 방법이 제대로 기억이 안나서 일단 생각나는대로 구현을 했는데 결과는 맞았지만 다른 사람들의 풀이와 내 풀이법을 비교해보니 나의 풀이가 좀 기괴?한 것 같아서 일단 다른 사람들의 풀이를 공부할 겸 리뷰를 적어보도록 한다.

 

📌 - 다른 사람들 풀이

1. graph와 visited의 2차원 배열을 만들어 놓고 graph에는 초기 토마토의 배치상태를 넣어두고, visited은 전부 -1로 초기화를 한 뒤 제일 처음 graph배열을 만들 때 토마토가 들어 있는 칸을 visited[i][j] = 0 으로 만들고 (i,j)를 큐에 넣고 시작한다.
2. 그리고 BFS를 큐가 빌때까지 돌면서 인접한 칸에 해당하는 graph[i][j]가 0이면 다시 (i,j) 큐에 넣어주고 큐에 넣으면서 visited를 이전에 방문했던 visited + 1 로 업데이트 해준다.
3. 이런식으로 큐가 빌때까지 계속해서 업데이트를 해주면 제일 마지막에 업데이트 된 visited는 정답인 날짜가 된다.
4. 그리고 마지막으로 전부 다 채워졌는지 확인하기 위해 처음부터 끝까지 배열을 돌면서 graph[i][j]는 0이지만 visited[i][j] == -1인 배열 => 빈 공간이지만 방문하지 못한 경우가 있으면 -1을 출력하고 그런 경우가 없다면 day를 출력하면서 정답이 나오게 된다.

🔥 - 다른 분의 Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int [] di = {0, 0, 1, -1};
	static int [] dj = {1, -1, 0, 0};
	static int w, h;
	static int [][] visit;
	static int [][] graph;
	static int day = 0;
	static Queue<Tomato> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		w = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		graph = new int[h][w];
		visit = new int[h][w];
		for (int i = 0; i < h; i++) {
			Arrays.fill(visit[i], -1);
		}

		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < w; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
				if (graph[i][j] == 1) {
					q.offer(new Tomato(i, j));
					visit[i][j] = 0;
				}
			}
		}
		
		while (!q.isEmpty()) {
			Tomato cur = q.poll();
			int ci = cur.i;
			int cj = cur.j;
			day = visit[ci][cj];

			for (int k = 0; k < 4; k++) {
				int ni = ci + di[k];
				int nj = cj + dj[k];
				if (0 <= ni && ni < h && 0 <= nj && nj < w) {
					if (graph[ni][nj] == 0 && visit[ni][nj] == -1) {
						visit[ni][nj] = visit[ci][cj] + 1;
						q.offer(new Tomato(ni, nj));
					}
				}
			}
		}

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (visit[i][j] == -1 && graph[i][j] == 0) {
					System.out.println(-1);
					return;
				}
			}
		}
		System.out.println(day);
	}
}
class Tomato {
	int i;
	int j;

	Tomato(int i, int j) {
		this.i = i;
		this.j = j;
	}
}

 

 

📌- 나의 풀이

1. 일단 처음부터 tomato 배열을 만들면서 1이면 큐에 집어넣고 -1일 경우에는 count를 해주면서 갯수를 세준다.
2. 그리고 BFS를 수행하게 되는데, 하나는 while문으로 무한루프를 돌게 하고 하나는 큐가 빌때까지 반복되는 while문을 사용하게 된다.
3. 첫번 째 큐가 빌때까지 인접한 칸이 0이라면 두번째 큐에 (i,j)를 집어 넣고 첫번째 큐가 비었다면 result(day) = +1을 해주고 다시 반복하게 된다.
4. 그리고 두번째 큐를 다시 첫번 째 큐로 복사를 하고 두번 째 큐는 초기화 시켜주면서 모든 값을 다 돌때까지 반복한다.
5. 여기서 첫번째 무한루프의 종료조건은 전체 배열에서 -1이 들어간 값을 제외한 나머지 값들이 전부 1이되면 되므로 1로 변경시켜줄때마다 더해준 ans와 N*M-minus가 같으면 모든 토마토가 익은 것이므로 종료 시키고 result(day)를 출력한다.
6. 그리고 전부 다 익을 수 없는 조건에는 이전 날짜에 익은 토마토 수와 오늘 익은 토마토수에 변함이 없다면 앞으로도 토마토는 익을 수 없기 때문에 이런 경우가 생길 경우 result(day)를 -1로 변경 시켜주고 BFS를 종료한다.

뭔가 다시 보면서도 조금 이상하게 짰나 싶기도 한데, 일단 메모리나 시간적인 부분에서는 별 차이가 없기 때문에 한번 적어봤고, 위의 방법처럼 visited를 사용해서 이전 날짜를 업데이트 해주는 식으로 해도 되게 간단하게 짤 수 있는 것 같다.

 

🔥 - Java 코드

 

package BFS.G5_7576_토마토;

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


class Locate{
    int x;
    int y;
    Locate(int x, int y){
        this.x = x;
        this.y = y;
    }
}
public class Main {
        public static int N,M,result =0,minus=0;
        public static int[][] tomato;
        public static Deque<Locate> deque;
    public static void main(String[] args) throws IOException {
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        tomato = new int[M][N];
        deque = new ArrayDeque<>();

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            for(int j =0; j<N;j++){
                int num = Integer.parseInt(st.nextToken());
                tomato[i][j] = num;
                if(num == 1){
                    deque.add(new Locate(i,j));
                }
                if(num == -1){
                    minus++;
                }
            }
        }

        BFS();
        System.out.println(result);

    }

    public static void BFS(){
        int[] dx= {0,0,1,-1};
        int[] dy= {1,-1,0,0};
        int ans =0;

        while(true){
            Deque<Locate> temp = new ArrayDeque<>();
            int test = ans;
            while(!deque.isEmpty()){
                Locate lc = deque.poll();
                ans++;
                for(int i=0;i<4;i++){
                    int nx = lc.x +dx[i];
                    int ny = lc.y +dy[i];
                    if(nx>=0 && nx<M && ny>=0 && ny<N && tomato[nx][ny] ==0){
                        tomato[nx][ny]=1;
                        temp.add(new Locate(nx,ny));

                    }
                }

            }

            deque = temp;
            if(ans == N*M-minus){
                break;
            }

            if(test == ans){
                result = -1;
                break;
            }
            result++;
        }


    }

}