[Eric's 백준] 7576번 - 토마토 - Java 🍅

문제

 

 

안녕하세요! Eric 입니다! 오늘 가져온 문제는 bfs로 풀 수 있는 

백준 7576번 토마토 문제 입니다!

 

그러면 문제풀이 시작해볼까요?

 

풀이

 

해당 문제는 bfs 로 풀 수 있는 문제입니다.

 

저는 해당 위치의 값을 class Point 라는 값으로 관리 하였습니다.

우선 토마토가 보관되는 창고에서 있는 input 값들을 입력해줍니다.

이때, 입력되는 값이 1 이면,

해당 토마토는 익은토마토이므로 옆으로 움직이면서 근처 토마토들을 익게 만들 수 있습니다.

그러면 익은 토마토 들이 bfs를 돌면서 상,하,좌,우 의 토마토들을 익게 만들어줍니다. ([]dx , []dy 이용)

이때 bfs를 돌면서 

board[][] 에 입력된 값이 1 이면, 

dis[][] 라는 동일한 크기의 배열에서 +1씩 추가해줍니다.

1씩 추가해준 이유는, Queue가 한턴 돌때마다 1일씩 추가 되므로

Queue가 빈통일 될때까지 돌아줍니다.

 

bfs를 다 돌고나서는

익지않은 토마토가 있는지 확인하기 위해서

다시 for문을 돕니다,

만약 board에 하나라도 0 이 존재하면,

이 토마토판은 다 익지 못하는 것이므로

마지막에 -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;
	class N7576 {
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q = new LinkedList<>(); // 전역으로 잡은 이유는 BFS 도 사용해야하지만, main 에서도 익은 토마토를 넣어야하기때문
	public static void bfs() {
	while (!Q.isEmpty()) {
	Point tmp = Q.poll();
	for (int i = 0; i < 4; i++) {
	int nx = tmp.x + dx[i];
	int ny = tmp.y + dy[i];
	if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 0) {
	board[nx][ny] = 1;
	Q.offer(new Point(nx, ny));
	dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
	}
	}
	}
	}
	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());
	n = Integer.parseInt(st.nextToken());
	board = new int[n][m];
	dis = new int[n][m];
	for (int i = 0; i < n; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < m; j++) {
	board[i][j] = Integer.parseInt(st.nextToken());
	if (board[i][j] == 1) Q.offer(new Point(i, j)); // 익은 토마토 넣어놓기 - 0 레벨
	}
	}
	// bfs 돌기
	bfs();
	boolean flag = true; // 익지 않은 토마토 검색용
	int answer = Integer.MIN_VALUE;
	//board 를 돌면서 값이 0인 값이 있으면 flag 를 false 로 만들어준다.
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (board[i][j] == 0) flag = false;
	}
	}
	// flag 값이 true 인 경우에만 max 값을 도출하도록 for문을 돈다.
	if (flag) {
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	answer = Math.max(answer, dis[i][j]);
	}
	}
	System.out.println(answer);
	} else System.out.println(-1);
	br.close();
	}
	}
	class Point {
	public int x, y;
	Point(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}

view raw N7576.java hosted with ❤ by GitHub