[JAVA] BOJ(백준) - 토마토 - 7576

- 문제 내용

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

7576번: 토마토

 

---

- 문제 접근 방법

익은 토마토 기준으로 상하좌우에 있는 익지 않은 토마토들이 하루가 지날때마다 익어가는 문제이므로 상하좌우의 토마토가 0인지 판단만 해준다면 풀수 있는 문제라고 생각했다.

그리고 주의할점은 처음에 익은 토마토는 여러개가 있을 수도 있어서 동시다발적으로 익어가는 상황도 고려해야한다는 점이다. 

그래서 처음에 큐에는 익은 모든 토마토들의 행과 열의 위치값을 저장하는 객체(Point)를 넣어주고 풀었다.

 

정리하면

1. 큐에 현재 익은 토마토의 위치값을 저장한 객체를 넣어준다.

2. 큐의 객체를 반환해서 상하좌우를 돌고 조건에 맞다면 0이었던 토마토를 현재 갖고 있는 바로직전의 토마토+1을 해준다.

3. +1해준 토마토의 위치값을 다시 큐에 넣어준다

4. 1~3을 큐가 빌때까지 반복한다.

5. 최대일수를 구해준다.

 

---

- 풀이

 

 큐에 넣을 객체를 만들때 필요한 클래스

class Point{ //행과 열의 위치 저장해줄 클래스
	int pointX;
	int pointY;
	public Point(int x, int y) {
		this.pointX = x;
		this.pointY = y;
	}
}

 

BFS

public void solution() {
		Queue<Point> queue = new LinkedList<Point>();
		
		for(int i=0; i<N; i++) { // 큐에 익은 토마토 일단 다 담기.
			for(int j=0; j<M; j++) {
				if(tomatoBox[i][j]==1 && !check[i][j]) {
					check[i][j]=true;
					queue.add(new Point(i,j));
				}
			}
		}
		bfs(queue);//bfs 구현
	}
	
	public void bfs(Queue<Point> queue) {
		
		while(!queue.isEmpty()) {
			Point p = queue.poll(); //Point 객체 생성후 큐에있던 객체 할당
			int nowX = p.pointX; //현재 행값
			int nowY = p.pointY; //현재 열값
			
			for(int i=0; i<4; i++) {
				int dx = nowX + x[i]; //다음 행값
				int dy = nowY + y[i]; //다음 열값
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) { //행과 열의 위치값은 이조건 만족해야함
					if(tomatoBox[dx][dy]==0 && !check[dx][dy]) {
						tomatoBox[dx][dy]=tomatoBox[nowX][nowY]+1; //다음 토마토 익혀버리기 
						queue.add(new Point(dx,dy)); //큐에 다시 행과 열의 위치값을 저장하는 객체를 넣어줌.
						check[dx][dy]=true;
					}else if(tomatoBox[dx][dy]==-1 && !check[dx][dy]) {
						check[dx][dy]=true;
					}//else if
				}//if
			}//for
		}//while
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(tomatoBox[i][j]==0) {//익지 않은 토마토가 있다면 -1출력후 끝냄.
					System.out.println(-1);
					return;
				}
				dayCnt=Math.max(dayCnt, tomatoBox[i][j]);//최대 일수 비교
			}
		}
		System.out.println(dayCnt-1);//첫 시작이 익은토마토에서 시작해서 1을 빼줘야됨.
	}

---

전체코드

package org.boj.dfs.bfs;

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

public class BOJ_7576 {
	static int M,N; // 입력값
	static boolean[][] check; // 방문배열
	static int[][] tomatoBox; 
	static int dayCnt; // 최대일수
	
	static int[] x = {0, 0, -1, 1}; //상하 좌우
	static int[] y = {-1, 1, 0, 0}; //상하 좌우
	
	public void solution() {
		Queue<Point> queue = new LinkedList<Point>();
		
		for(int i=0; i<N; i++) { // 큐에 익은 토마토 일단 다 담기.
			for(int j=0; j<M; j++) {
				if(tomatoBox[i][j]==1 && !check[i][j]) {
					check[i][j]=true;
					queue.add(new Point(i,j));
				}
			}
		}
		bfs(queue);//bfs 구현
	}
	
	public void bfs(Queue<Point> queue) {
		
		while(!queue.isEmpty()) {
			Point p = queue.poll(); //Point 객체 생성후 큐에있던 객체 할당
			int nowX = p.pointX; //현재 행값
			int nowY = p.pointY; //현재 열값
			
			for(int i=0; i<4; i++) {
				int dx = nowX + x[i]; //다음 행값
				int dy = nowY + y[i]; //다음 열값
				
				if(dx>=0 && dy>=0 && dx<N && dy<M) { //행과 열의 위치값은 이조건 만족해야함
					if(tomatoBox[dx][dy]==0 && !check[dx][dy]) {
						tomatoBox[dx][dy]=tomatoBox[nowX][nowY]+1; //다음 토마토 익혀버리기 
						queue.add(new Point(dx,dy)); //큐에 다시 행과 열의 위치값을 저장하는 객체를 넣어줌.
						check[dx][dy]=true;
					}else if(tomatoBox[dx][dy]==-1 && !check[dx][dy]) {
						check[dx][dy]=true;
					}//else if
				}//if
			}//for
		}//while
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(tomatoBox[i][j]==0) {//익지 않은 토마토가 있다면 -1출력후 끝냄.
					System.out.println(-1);
					return;
				}
				dayCnt=Math.max(dayCnt, tomatoBox[i][j]);//최대 일수 비교
			}
		}
		System.out.println(dayCnt-1);//첫 시작이 익은토마토에서 시작해서 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());

		tomatoBox = new int[N][M];
		check = new boolean[N][M];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				tomatoBox[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		new BOJ_7576().solution();
	}
}

class Point{ //행과 열의 위치 저장해줄 클래스
	int pointX;
	int pointY;
	public Point(int x, int y) {
		this.pointX = x;
		this.pointY = y;
	}
}

---

- 마치며

미로탐색 문제를 풀어보고 동시다발적으로 시작하는 점을 고려해 처음에 큐에 모든 1의 객체를 넣어주는 생각만 한다면 크게 어려운 문제는 아니였다.

아쉬운점이 있다면 BFS 풀이에서 방문배열은 어차피 토마토박스 배열이 1씩 증가하면서 알려주기 때문에 필요없는데 쓴것과 -1일때 경우도 필요없고 그냥 0일때의 경우만 판단하면 되는 문제인데 괜히 필요도 없는데 코드를 추가한부분이 아쉽다.