[백준알고리즘-JAVA]7576번 풀이(토마토) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 7576번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 7576(토마토)

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

 

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M, NM, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

 

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 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;

public class Main {

	static boolean[][] check;
	static int[][] arr;
	static int[] moveX = {0, 0, 1, -1};
	static int[] moveY = {1, -1, 0, 0};
	static int count = 0,ans = Integer.MIN_VALUE;
	static Queue<spot> q = new LinkedList<>();
	static int N, M;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));				
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[M][N];
		check = new boolean[M][N];
		for(int i = 0 ; i < M ; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			for(int j = 0 ; str.hasMoreTokens() ; j++) {
				arr[i][j] = Integer.parseInt(str.nextToken());
				if(arr[i][j] == 1)
					q.add(new spot(i,j));
			}
		}
		
		while(!q.isEmpty()) {
			spot s = q.poll();
		int x = s.x;
		int y = s.y;
		System.out.println( x + " : " + y);
		check[x][y] = true;
		 bfs(x,y);
		check = new boolean[M][N];
		}
		
		loop : for(int i = 0 ; i < M ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(arr[i][j] == 0) {
					ans = 0;
					break loop;
				}else {
					ans = Math.max(ans, arr[i][j]);
				}
		}
		}
			System.out.println(ans-1);
		}

	public static void bfs(int x, int y) {
		
		Queue<spot> temp = new LinkedList<>();
		temp.add(new spot(x,y));
		
		while(!temp.isEmpty()) {
			spot s = temp.poll();
			for (int i = 0; i < 4; i++) {
                int nextX = s.x + moveX[i];
                int nextY = s.y + moveY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
                    continue;
                }
                if (check[nextX][nextY] || arr[nextX][nextY] < 0) {
                    continue;
                }
                temp.add(new spot(nextX, nextY));
                if(arr[nextX][nextY] == 0)
                	arr[nextX][nextY] = arr[s.x][s.y] + 1;
                else
                	arr[nextX][nextY] = Math.min(arr[s.x][s.y] + 1, arr[nextX][nextY]);

                check[nextX][nextY] = true;
            }
		}
	}
}
class spot{
	int x;
	int y;
	spot(int x, int  y){
		this.x = x;
		this.y = y;
	}
}

 해당 코드는 정답은 맞지만 시간 초과가 나는 코드이다. 해당 코드는 큐를 활용해서 진행하는 과정이었는데 해당 코드에서 시간 초과가 나는 이유는 bfs를 while을 통해서 모든 위치에서 작동했기 때문이라고 생각한다. 그러나 생각해보면 굳이 모든 곳을 방문할 필요는 없다. 왜냐하면 토마토가 익기 위해서는 무조건 이어져있어야 한다. 이에 따라서 모든 배열에는 1 아니면 -1만이 존재해야 한다. 이를 고려하여 다시 코드를 수정한다.

성공코드

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

public class Main {

	static boolean[][] check;
	static int[][] arr;
	static int[] moveX = {0, 0, 1, -1};
	static int[] moveY = {1, -1, 0, 0};

	static int count = 0,ans = Integer.MIN_VALUE;
	static Deque<spot> q = new LinkedList<>();

	
	static int N, M;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[M][N];
		check = new boolean[M][N];
		
		for(int i = 0 ; i < M ; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			for(int j = 0 ; str.hasMoreTokens() ; j++) {
				arr[i][j] = Integer.parseInt(str.nextToken());
				if(arr[i][j] == 1)
					q.add(new spot(i,j));
			}
		}
		 bfs();
		loop : for(int i = 0 ; i < M ; i++) {
			for(int j = 0 ; j < N ; j++) {
				//System.out.print(arr[i][j] + " ");
				if(arr[i][j] == 0) {
					ans = 0;
					break loop;
				}else
					ans = Math.max(ans, arr[i][j]);
		}
		}
		
			System.out.println(ans-1);
		}

	public static void bfs() {
		
		while(!q.isEmpty()) {
			spot s = q.poll();
			for (int i = 0; i < 4; i++) {
                int nextX = s.x + moveX[i];
                int nextY = s.y + moveY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
                    continue;
                }
                if (check[nextX][nextY] || arr[nextX][nextY] < 0) {
                    continue;
                }
                
                q.add(new spot(nextX, nextY));
                if(arr[nextX][nextY] == 0)
                	arr[nextX][nextY] = arr[s.x][s.y] + 1;
                else
                	arr[nextX][nextY] = Math.min(arr[s.x][s.y] + 1, arr[nextX][nextY]);
                
                check[nextX][nextY] = true;
            }
		}
	}
}
class spot{
	int x;
	int y;
	spot(int x, int  y){
		this.x = x;
		this.y = y;
	}
}

앞선 실패 코드를 고치기 위해서 while문 하나를 삭제하고 입력을 받을 때 해당 값을 q에 넣어준 뒤 바로 bfs를 인자 전달 없이 실행시키는 방법으로 수정하였다. 코드가 훨씬 간결해짐을 알 수 있었다.

---

알고리즘 흐름도

 입력받기 -> 큐에 값 넣기 arr 초기화 하기 -> bfs 실행하기 -> 값이 하나라도 0이라면 오류 출력 아니라면 답 출력

---

STEP1 큐에 값 넣고 arr 초기화하기

		for(int i = 0 ; i < M ; i++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			for(int j = 0 ; str.hasMoreTokens() ; j++) {
				arr[i][j] = Integer.parseInt(str.nextToken());
				if(arr[i][j] == 1)
					q.add(new spot(i,j));
			}
		}

 간단합니다. 2중 for문을 활용하여 stringtokenizer로 입력값을 구분해 주며 만약 해당 값이 1이라면 q에 추가해 줍니다.

여기서 spot은 해당 점의 x, y좌표를 가진 오브젝트입니다.

---

STEP2 bfs 구현하기

 이제는 간단한 bfs의 구현은 쉽게 할 수 있는데요

	public static void bfs() {
		
		while(!q.isEmpty()) {
			spot s = q.poll();
			for (int i = 0; i < 4; i++) {
                int nextX = s.x + moveX[i];
                int nextY = s.y + moveY[i];
                
                if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
                    continue;
                }
                if (check[nextX][nextY] || arr[nextX][nextY] < 0) {
                    continue;
                }
                
                q.add(new spot(nextX, nextY));
                if(arr[nextX][nextY] == 0)
                	arr[nextX][nextY] = arr[s.x][s.y] + 1;
                else
                	arr[nextX][nextY] = Math.min(arr[s.x][s.y] + 1, arr[nextX][nextY]);
                
                check[nextX][nextY] = true;
            }
			
		}
	}

 그리 어렵지 않습니다. 처음에 입력을 받을 때 q에 저장했던 1의 값들을 시작으로 합니다.

 

 해당 값을 꺼내고 동서남북으로 이동하며 확인합니다.

 - 범위를 넘었으면 continue 실행하여 다른 방향 탐색

 - 해당 값이 -1이면 다른 방향 탐색

 - 2가지 모두 해당되지 않는다면 q에 해당 지점을 저장

 - 해당 좌표의 값이 0이라면 해당 값을 이동하기 전 값의 +1을 해줍니다. (bfs방식이죠)

 - 만약 0이 아니라면 비교합니다. 이전 값에서 +1을 하는 것과 arr 이동 방향에 있는 값과 더 작은 것을 넣어줍니다.

(더 빠르게 오는 게 해당 값에 들어가는 게 맞다.)

 

지금 다시 생각해보면 만약 else로 저렇게 처리한다면 굳이 check배열은 없어도 될 듯싶다.

---

STEP 3 답 도출하기

		loop : for(int i = 0 ; i < M ; i++) {
			for(int j = 0 ; j < N ; j++) {
				if(arr[i][j] == 0) {
					ans = 0;
					break loop;
				}else
					ans = Math.max(ans, arr[i][j]);
		}
		}

 반복문 2개를 통해서 arr의 값에 하나라도 0 이 있으면 오류 출력하기 위해 ans에 0을 넣고 2중 for문을 빠져나옵니다. 그게 아니라면 최댓값이 무엇인지 찾습니다.

 

 만약 오류가 하나도 없다면 최댓값이 ans에 담기게 되죠. 마지막에 ans만 출력하면 끝!