[JAVA 자바] 백준 7576번 : 토마토

▶ 문제

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

7576번: 토마토

 

▶ 설명

토마토 상자에서 익은 토마토는 1, 익지 않은 토마토는 0, 토마가 아닌 곳은 -1으로 표시된다.

예제 3에서 익은 토마토는 2개이고,  익은 토마토에서 익지 않은 근접한 토마토로 1씩 방문 카운트를 증가시킨다.

-1라고 되어 있는  곳은 토마토가 없으므로 방문을 하지 않는다.

 

 

 

 

 

처음 Queue에 저장되는 데이터

단계별로 풀어보기 문제 중에서 이전 문제였던 미로 탐색과 비교해보자면 

미로탐색 문제는 출발점이 하나인 반면 이 문제에서는 여러개가 될 수 있다는 점이다.

즉, Queue 에 처음 데이터를 넣을 때 한 개가 아니라 한 개 이상이 들어갈 수 있다는 의미이다.

위의 예제를 살펴보면, 1인 곳의 인덱스 [0,0]와 [3,5]가 Queue에 처음 저장된다.

 

익은 토마토는 ArrayList에 저장하기.

익은 토마토가 몇 개 있는지 미리 입력에서 주어지지 않으므로 토마토 상자를 2차 배열로 입력받아 생성할 때, 값이 1인 곳은 ArrayList로 그 인덱스 (위치)를 저장하도록 해야 한다.

 

 

 

 

 

 

 

▶ 문제 풀이

🌱 풀이. 

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

public class Main {
	static int m, n; // 토마토 바구니 크기.
	static int[][] basket; // 토마토 바구니
    // 첫날 익어있는 토마토의 위치 (입력값이 1인 index 묶음들을 저장하기)
	static ArrayList<Tomato> list = new ArrayList<>(); 

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		m = Integer.parseInt(st.nextToken());// 세로 칸의 수. column
		n = Integer.parseInt(st.nextToken());// 가로 칸의 수. row

		basket = new int[n][m];

		for (int i = 0; i < basket.length; i++) {
			String line = br.readLine();
			st = new StringTokenizer(line, " ");
			for (int j = 0; j < basket[i].length; j++) {
				basket[i][j] = Integer.parseInt(st.nextToken());
				// 익은 토마토 1이 나타나면 index인 x,y를 list에 저장하기.
				if (basket[i][j] == 1) {
					list.add(new Tomato(i, j));
				}
			}
		}

		// bfs 에서 날짜 셀 때 하루가 추가되었으므로 출력할 때 1일을 빼줘야 함.
		int result = bfs() - 1; 

		// 토마토 바구니를 전체 검사해서 0이 존재했을 시 -1 출력하도록 하기.
		Loop: for (int i = 0; i < basket.length; i++) {
			for (int j = 0; j < basket[i].length; j++) {
				if (basket[i][j] == 0) {
					result = -1;
					break Loop; // 0을 찾으면 출력값에 -1 저장하고 바로 반복문 종료.
				}
			}
		}
		System.out.println(result);

	}

	private static int bfs() {
		int[] aX = { 0, 0, -1, 1 }; // around x. 가로로 이동하며 탐색
		int[] aY = { -1, 1, 0, 0 }; // around y. 세로로 이동하며 탐색

		Queue<Tomato> q = new LinkedList<>();

		// 첫날 이미 익어있는 토마토들을 모두 Queue 에 넣기. 
        // 값이 1인 토마토의 위치가 담긴 list에서 데이터를 읽어와 Queue로 넣어준다.		
        for (int i = 0; i < list.size(); i++) {
			q.offer(list.get(i));
		}

		// Queue 안이 빌 때까지 반복하기.
		while (!q.isEmpty()) {

			// q에서 빼낸 토마토의 위치인 인덱스 번호 x,y를 가지고 좌,우,위,아래 위치들을 검색하기
			Tomato tomatoXY = q.poll();
			x = tomatoXY.getX(); // tomatoXY의 x좌표
			y = tomatoXY.getY(); // tomatoXY의 y좌표
			

			for (int j = 0; j < 4; j++) {
				int newX = x + aX[j];
				int newY = y + aY[j];

				// 토마토 바구니를 벗어난 위치라면 배열의 인덱스로 들어갈 시 
                // IndexOutOfBoundsException 예외가 발생하므로 사전에 범위를
				// 벗어났는지 확인한 후 무시하기.
				if (newX >= n || newX < 0 || newY >= m || newY < 0) {
					continue;
				}
				// 토마토 바구니 범위를 벗어나지 않는 배열의 인덱스인 경우 중에서 
                // 값이 0일 때 하루를 더해주고 q에 넣기. (값이 0이 아닌 1인 경우 자동으로 무시됨)
			
				if (basket[newX][newY] == 0) {
					basket[newX][newY] = basket[x][y] + 1;
					q.offer(new Tomato(newX, newY));
				}
			}
		}

		return basket[x][y]; // 마지막으로 q에 저장된 인덱스의 위치 x,y의 배열의 값을 반환. 
	}

}

class Tomato {
	private int x;
	private int y;

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

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}
}

 

 

입력되는 토마토 상자의 토마토 상태는 2차 배열로 만들되, Queue에 저장되는 데이터는 객체로 만들었다. 

미로탐색 문제에서처럼 방문한 토마토의 동서남북을 탐색하여 조건에 맞는 곳을 Queue에 넣은 뒤, 방문 카운트를 1씩 증가해 주도록 한다. 

모든 탐색과 방문을 마쳤으면 마지막에 방문한 곳의 위치인 인덱스 값으로 방문 카운트한 값을 반환해 주면 된다.