[7576번] 토마토 ( bfs, 반복문안에 queue 삽입, bfs는 최단거리!, 여러 개의 출발점에서 번갈아가며 bfs 실행가능 )

---

하다가 맞왜틀 이틀 동안 한 것 같은데, 해탈하고 정답인 코드 따라서 그냥 쳐보고 결과 확인하면서 동작원리 파악하다보니까 틀린 부분을 알 수 있었다.

맞왜틀이 너무 시간이 오래 걸린다 싶으면 정답인 코드 따라쳐보고 파악해보자!

---

✅ bfs가 한 번만 실행되는 이유

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (A[i][j] == 1) {
					System.out.println(i + " " + j);
//					visited = new boolean[n][m];
					bfs(i, j);
				}
			}
		}

아니 왜 도대체 여기서 0,0만 실행되는 거임!!??? 하 난 모르겠다.
블로그 참고한 대로 그냥 queue에 add해보자.

---

⭐️ Queue에 번갈아 가면서 입력

아 (0,0)들어가고 (3,5)들어가니까 두 개 시작점이 번갈아가면서 시작되도록 하려면 queue에 add를 반복문에서 해줘야 하는 거구나. 함수로 빼서 하면 안되는 구나.

	for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (A[i][j] == 1) {
					queue.add(new int[] {i, j});
					visited[i][j] = true;
				}
			}
		}

그러니까 queue앞에 새로운 bfs를 실행하는 것처럼 방문 배열을 다시 초기화해 줄 필요는 없는 것!!!이구나

그러면 이제 해줘야 할 거는 최소를 찾아줘야 함.!-> 아니네?
bfs해서 +1 한게 최소가 되는건가?
아 맞다!! 최단 거리다!! -> 시작점에서 자기 자신까지의 최단 거리 (미로 탐색 문제 참고)
그리고 접점이 멀다면 3,5에서 시작한 토마토는 5일째에 다익었어도 0,0에서 시작한 토마토가 6일째에 다 익을 수 있다.

그리고 끝까지 도착못하면 0이 존재하니까, 존재하면 return false해준다.

---

✅ 코드

-1 해주는 건 당연하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int m, n;
	static int[][] A;
	static boolean[][] visited;
	//우하좌상
	static int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

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

		A = new int[n][m];
		visited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Queue<int[]> queue = new LinkedList<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (A[i][j] == 1) {
					queue.add(new int[] {i, j});
					visited[i][j] = true;
				}
			}
		}


		while (!queue.isEmpty()) {
			int now[] = queue.poll();
			for (int k = 0; k < 4; k++) {
				int nowX = now[0] + dx[k];
				int nowY = now[1] + dy[k];
				if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
					if (!visited[nowX][nowY] && A[nowX][nowY] != -1) {
						visited[nowX][nowY] = true;
						A[nowX][nowY] = A[now[0]][now[1]] + 1;
						queue.add(new int[] {nowX, nowY});
					}
				}
			}
		}

		int Max = 0;

		if (!checkZero()) {
			System.out.println(-1);
			return;
		} else {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (A[i][j] > Max) {
						Max = A[i][j];
					}
				}
			}
			System.out.println(Max - 1);
		}

	}

	private static boolean checkZero() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (A[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}

}

---