[Java/백준/BFS] 7576번, 7569번: 토마토

문제 (2차원 배열)

www.acmicpc.net/problem/7576

7576번: 토마토

 

코드

백준 미로 탐색 문제와 비슷한듯 다르다.

토마토 문제는 익은 토마토로부터 검사를 시작하는데, 그 갯수를 알 수 없기 때문이다.

다행히 입력할 때부터 선언한 queue 안에 익은 토마토의 좌표를 넣어주면 된다는 것을 알게 되었다.^__^

 

bfs 함수

queue 안에는 익은 토마토의 좌표가 들어있다.

검사할 토마토의 사방을 보았을 때, >> 안익은 토마토일 것 && 지나간 적이 없어야 할 것 << 이 조건을 만족해야 한다.

조건을 만족하면 토마토를 익은 상태로 바꾸어 주고, 며칠째에 바뀐 것인지도 입력해준다.

 

answer는 visited 배열 중 가장 큰 수가 들어간다. 별 다른 이상이 없으면 answer가 리턴된다.

tomatoes 배열 전체를 검사해서 안익은 토마토가 있다면 -1을 리턴한다.

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

class Node{
	int x;
	int y;
	Node(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Main {
	static int n;
	static int m;
	static int[][] visited;
	static int[][] tomatoes;
	static int[] dx = {0,0,-1,1};
	static int[] dy = {-1,1,0,0};
	static Queue<Node> queue = new LinkedList<>();
	
	public static int bfs() {
		while(!queue.isEmpty()) {
			Node r = queue.poll();
			int x = r.x;
			int y = r.y;
			for(int i=0; i<4; i++) {
				if(x+dx[i]<0 || x+dx[i]>=n || y+dy[i]<0 ||y+dy[i]>=m)
					continue;
				else if(tomatoes[x+dx[i]][y+dy[i]]==0 && visited[x+dx[i]][y+dy[i]]==0) {
					visited[x+dx[i]][y+dy[i]]=visited[x][y]+1;
					tomatoes[x+dx[i]][y+dy[i]]=1;
					queue.offer(new Node(x+dx[i],y+dy[i]));
				}
			}
		}
		
		int answer = 0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				answer = Math.max(answer, visited[i][j]);
				if(tomatoes[i][j]==0) {
					return -1;
				}
			}
		}
		return answer;
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String cond = br.readLine();
		m = Integer.parseInt(cond.split("\\s")[0]);
		n = Integer.parseInt(cond.split("\\s")[1]);
		tomatoes = new int[n][m];
		visited = new int[n][m];
		for(int i=0; i<n; i++) {//세로
			String[] str = br.readLine().split("\\s");
			for(int j=0; j<m; j++) {//가로
				tomatoes[i][j] = Integer.parseInt(str[j]);
				if(tomatoes[i][j]==1)
					queue.offer(new Node(i,j));
			}
		}
		
		bw.write(Integer.toString(bfs())+"\n");
		bw.flush();
		
	}
}

 

문제 (3차원 배열)

www.acmicpc.net/problem/7569

7569번: 토마토

 

코드

Node 클래스에 z만 추가해주면 된다

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node{
	int x;
	int y;
	int z;
	public Node(int z, int y, int x) {
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

class Main{
	static int[][][] visited;
	static int[][][] tomatoes;
	static int M;
	static int N;
	static int H;
	
	static Queue<Node> queue = new LinkedList<Node>();
	
	//왼 오 평면아래 평면위 아래 위
	static int[] dx = {-1, 1, 0, 0, 0, 0};
	static int[] dy = {0, 0, -1, 1, 0, 0};
	static int[] dz = {0, 0, 0, 0, -1, 1};
	
	static String bfs() {
		while(!queue.isEmpty()) {
			Node first = queue.poll();
			int x = first.x;
			int y = first.y;
			int z = first.z;
			
			for(int i=0; i<6; i++) {
				int tmpX = x+dx[i];
				int tmpY = y+dy[i];
				int tmpZ = z+dz[i];
				if(tmpX<0 || tmpX>=M || tmpY<0 || tmpY>=N || tmpZ<0 || tmpZ>=H) {
					continue;
				}else if(tomatoes[tmpZ][tmpY][tmpX]==0 && visited[tmpZ][tmpY][tmpX]==0) {
					visited[tmpZ][tmpY][tmpX]=visited[z][y][x]+1;
					tomatoes[tmpZ][tmpY][tmpX]=1;
					queue.offer(new Node(tmpZ, tmpY, tmpX));
				}
			}
		}
		
		int answer=0;
		
		for(int h=0; h<H; h++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<M; j++) {
					answer = Math.max(visited[h][i][j], answer);
					if(tomatoes[h][i][j]==0) {
						return "-1";
					}
				}
			}
		}
		return Integer.toString(answer);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] nums = br.readLine().split(" ");
		M = Integer.parseInt(nums[0]); //가로
		N = Integer.parseInt(nums[1]); //세로
		H = Integer.parseInt(nums[2]); //높이
		
		visited = new int[H][N][M];
		tomatoes = new int[H][N][M];
		
		for(int h=0; h<H; h++) {
			for(int i=0; i<N; i++) {
				String[] line = br.readLine().split(" ");
				for(int j=0; j<M; j++) {
					tomatoes[h][i][j] = Integer.parseInt(line[j]);
					if(tomatoes[h][i][j]==1)
						queue.offer(new Node(h, i, j));
				}
			}
		}
			
		
		bw.write(bfs()+"\n");
		bw.flush();
	}
}