7576

1. 토마토

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

2. 나만의 문제 해결

그래프 탐색 문제 -> BFS DFS 중 하나로 해결 가능

1. 방문을 확인하기 위한 2차원 배열 1개
2. BFS를 이용해 익은 토마토와 이어진 노드를 방문 확인
3. 익은 토마토가 여러개일 경우는 여러시작점을 가진다
4. BFS 후 에도 아직 안익은 토마토가 있다 = -1

---

3. code

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		m = scanner.nextInt();
		n = scanner.nextInt();
		map = new int[n][m];
		int max = 0;
		boolean flag = false;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = scanner.nextInt();
				if (map[i][j] == 1){
					tx.add(i);
					ty.add(j);
				}
			}
		}

		BFS();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0) {
					flag = true;
				}
				if (max < map[i][j]){
					max = map[i][j];
				}
			}
		}

		if (flag)
			System.out.println(-1);
		else
			System.out.println(max-1);
	}
    
    public static void BFS(){
		int x;
		int y;

		Queue<Integer> queue = new ArrayDeque<>(n*m);

		for (int i = 0; i < tx.size(); i++) {
			queue.add(tx.get(i));
			queue.add(ty.get(i));
		}

		while(!queue.isEmpty()){
			x = queue.poll();
			y = queue.poll();

			//왼쪽
			if (x > 0){
				if (map[x - 1][y] == 0){
					map[x - 1][y] = map[x][y] + 1;
					queue.add(x-1);
					queue.add(y);
				}
			}
			//오른쪽
			if (x < n-1) {
				if (map[x + 1][y] == 0){
					map[x + 1][y] = map[x][y] + 1;
					queue.add(x+1);
					queue.add(y);
				}
			}
			//위
			if (y > 0){
				if (map[x][y - 1] == 0) {
					map[x][y - 1] = map[x][y] + 1;
					queue.add(x);
					queue.add(y - 1);
				}
			}
			//아래
			if (y < m-1) {
				if (map[x][y + 1] == 0) {
					map[x][y + 1] = map[x][y] + 1;
					queue.add(x);
					queue.add(y + 1);
				}
			}
		}
	}