[백준-7576번/Java] 토마토

* BFS ; queue 사용

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

public class Main {
	static int[][] arr; // 전체 상태 배열
	static Queue<Cann> agedTomato; // 숙성된 토마토 칸 배열
	static int M;
	static int N;
	static int day = 0;

	private static class Cann {
		int x;
		int y;

		public Cann(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Cann) {
				return x == ((Cann) o).x && y == ((Cann) o).y;
			} else {
				return false;
			}
		}

		@Override
		public int hashCode() {
			return Objects.hash(x, y);
		}

		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return "(" + x + ", " + y + ")";
		}

	}

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

		StringTokenizer mn = new StringTokenizer(br.readLine(), " ");

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

		arr = new int[N][M];
		agedTomato = new LinkedList<Cann>();

		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int value = Integer.parseInt(stk.nextToken());
				arr[i][j] = value;
				if (value == 1 || value == -1) {
					agedTomato.add(new Cann(i, j));
				}
			}
		}

		if (aging()) {
			System.out.println(day);
		} else {
			System.out.println(-1);
		}

	}

	private static boolean aging() {

		while (!agedTomato.isEmpty()) {
			Cann cann = agedTomato.poll();
			int i = cann.x;
			int j = cann.y;

			if (arr[i][j] >= 1) {
				if (i - 1 >= 0 && arr[i - 1][j] == 0) { // 상
					agedTomato.add(new Cann(i - 1, j));
					arr[i - 1][j] = arr[i][j] + 1;
				}
				if (i + 1 < N && arr[i + 1][j] == 0) { // 하
					agedTomato.add(new Cann(i + 1, j));
					arr[i + 1][j] = arr[i][j] + 1;
				}
				if (j - 1 >= 0 && arr[i][j - 1] == 0) { // 좌
					agedTomato.add(new Cann(i, j - 1));
					arr[i][j - 1] = arr[i][j] + 1;
				}
				if (j + 1 < M && arr[i][j + 1] == 0) { // 우
					agedTomato.add(new Cann(i, j + 1));
					arr[i][j + 1] = arr[i][j] + 1;
				}
				day = arr[i][j] - 1;
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (arr[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}
}

 

* HashSet 으로 풀면 시간초과 남..

* HashSet 중복 체크하는 법

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

public class Main {
	static int[][] arr; // 전체 상태 배열
	static HashSet<Cann> agedTomato; // 숙성된 토마토 칸 배열
	static int M;
	static int N;
	static int wholeCount = 0;

	private static class Cann {
		int x;
		int y;

		public Cann(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof Cann) {
				return x == ((Cann) o).x && y == ((Cann) o).y;
			} else {
				return false;
			}
		}

		@Override
		public int hashCode() {
			return Objects.hash(x, y);
		}

	}

	private static int aging() {
		HashSet<Cann> changedCann = new HashSet<Cann>(); // 상태가 바뀐 토마토 칸 배열

		for (Cann cann : agedTomato) {
			int i = cann.x;
			int j = cann.y;

			if (arr[i][j] == 1) {
				if (i - 1 >= 0 && arr[i - 1][j] == 0) { // 상
					changedCann.add(new Cann(i - 1, j));
				}
				if (i + 1 < N && arr[i + 1][j] == 0) { // 하
					changedCann.add(new Cann(i + 1, j));
				}
				if (j - 1 >= 0 && arr[i][j - 1] == 0) { // 좌
					changedCann.add(new Cann(i, j - 1));
				}
				if (j + 1 < M && arr[i][j + 1] == 0) { // 우
					changedCann.add(new Cann(i, j + 1));
				}
			}
		}

		// 바뀐 상태값 반영
		for (Cann cann : changedCann) {
			agedTomato.add(cann);
			arr[cann.x][cann.y] = 1;
		}

		return changedCann.size();
	}

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

		StringTokenizer mn = new StringTokenizer(br.readLine(), " ");

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

		arr = new int[N][M];
		agedTomato = new HashSet<Cann>();

		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int value = Integer.parseInt(stk.nextToken());
				arr[i][j] = value;
				if (value == 1 || value == -1) {
					agedTomato.add(new Cann(i, j));
				}
			}
		}

		// 모든 토마토가 익는 날짜
		int day = 0;
		while (true) {
			int count = aging();
			if (count == 0)
				break;
			else
				day++;
		}

		if (agedTomato.size() == N * M) {
			System.out.println(day);
		} else {
			System.out.println(-1);
		}

	}

}