No7576 토마토 (너비 우선 탐색)

너비 우선 탐색을 이용한 문제풀이다. 전에 사용해봤던 방식은 토마토 박스의 모든 공간를 좌표를 key, 토마토 객체를, value 값으로 하여 HashMap에 넣었다. 하루가 지날 때마다 박스의 모든 공간을 검색하여 그날 익어야 할 토마토를 찾아놓은 후 익게 하는 방식으로 풀어보았다. 하지만 매일마다 모든 토마토를 검색해야 하기에 시간 초과를 피할 수 없었다.

 

https://6cessfuldev.tistory.com/17

No7576 토마토 (HashMap의 Custom key 만들어 풀어보기)

 

 

이번 방식은 너비 우선 탐색을 활용하였다. 먼저 좌표, 익은 날짜, 그리고 상태를 담은 토마토 클래스를 만들었다.

static class Tomato {
		int x;
		int y;
		int day;
		int status;
		
		public Tomato(int x, int y, int day, int status) {
			this.x = x;
			this.y = y;
			this.day = day;
			this.status = status;
		}
	}

  

그리고 박스 공간들이 방문되었는지 확인할 수 있는 boolean 배열과 Tomato 객체를 담은 Tomato 배열을 입력 받는다.

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strArr = br.readLine().split(" ");
		m = Integer.parseInt(strArr[0]);
		n = Integer.parseInt(strArr[1]);
		
		map=new Tomato[n][m];
		visit=new boolean[n][m];
		for (int i = 0; i < n; i++) {
			String[] strArr2 = br.readLine().split(" ");
			for (int j = 0; j < m; j++) {
				Tomato tm = new Tomato(i,j,0,Integer.parseInt(strArr2[j]));
				map[i][j]=tm;
						
			}
		}
    }

 

그리고 너비 우선 탐색 알고리즘을 바탕으로 queue<Tomato>를 사용한 탐색 메소드를 만들고 큐에 담아 너비 우선 탐색의 순서대로 꺼낼 때 사방의 토마토가 있고 상태가 0인 경우 사방의 토마토의 익은 날짜를 자신의 익은 날짜보다 하루 더 늦게 설정한다. 

 

	static void bfs() {
		
		Queue<Tomato> que = new LinkedList<>();
		
		//map이 1인 경우 사방의 좌표를 익어야 할 que에 저장
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if(map[i][j].status==1) {
					Tomato tm = new Tomato(i,j,0,1);
					que.add(tm);
					visit[i][j]=true;
				}
			}
		}
		
		while(!que.isEmpty()) {
			
			Tomato tom = que.poll();
			for (int i = 0; i < 4; i++) {
				int tmpx=tom.x+arrX[i];
				int tmpy=tom.y+arrY[i];
				
				if(tmpx>=0 && tmpx<n && tmpy>=0 && tmpy<m &&!visit[tmpx][tmpy]) {
					visit[tmpx][tmpy]=true;
					if(map[tmpx][tmpy].status==0) {
						Tomato tm = new Tomato(tmpx, tmpy,tom.day+1,1);
						que.add(tm);
						map[tmpx][tmpy].status=1;
						map[tmpx][tmpy].day=tom.day+1;
					}
				}
				
			}
			
		}
	}

이후 주어진 조건에 맞게 출력한다. 전체 소스는 아래와 같다.

package com.yuk;

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

public class No7576_2 {

	static int m;
	static int n;
	static Tomato[][] map;
	static boolean[][] visit;
	static int[] arrX = {0,1,0,-1};
	static int[] arrY = {1,0,-1,0};
	static ArrayList<Tomato> box = new ArrayList<>();
	
	static void bfs() {
		
		Queue<Tomato> que = new LinkedList<>();
		
		//map이 1인 경우 사방의 좌표를 익어야 할 que에 저장
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if(map[i][j].status==1) {
					Tomato tm = new Tomato(i,j,0,1);
					que.add(tm);
					visit[i][j]=true;
				}
			}
		}
		
		while(!que.isEmpty()) {
			
			Tomato tom = que.poll();
			for (int i = 0; i < 4; i++) {
				int tmpx=tom.x+arrX[i];
				int tmpy=tom.y+arrY[i];
				
				if(tmpx>=0 && tmpx<n && tmpy>=0 && tmpy<m &&!visit[tmpx][tmpy]) {
					visit[tmpx][tmpy]=true;
					if(map[tmpx][tmpy].status==0) {
						Tomato tm = new Tomato(tmpx, tmpy,tom.day+1,1);
						que.add(tm);
						map[tmpx][tmpy].status=1;
						map[tmpx][tmpy].day=tom.day+1;
					}
				}
				
			}
			
		}
	}
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strArr = br.readLine().split(" ");
		m = Integer.parseInt(strArr[0]);
		n = Integer.parseInt(strArr[1]);
		
		map=new Tomato[n][m];
		visit=new boolean[n][m];
		for (int i = 0; i < n; i++) {
			String[] strArr2 = br.readLine().split(" ");
			for (int j = 0; j < m; j++) {
				Tomato tm = new Tomato(i,j,0,Integer.parseInt(strArr2[j]));
				map[i][j]=tm;
						
			}
		}
		
		bfs();
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(map[i][j].status==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		int max = 0;
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if(max < map[i][j].day) {
					max = map[i][j].day;
				}
			}
		}
		System.out.println(max);
		
	
	}

	static class Tomato {
		int x;
		int y;
		int day;
		int status;
		
		public Tomato(int x, int y, int day, int status) {
			this.x = x;
			this.y = y;
			this.day = day;
			this.status = status;
		}
	}
}