[백준]BFS 알고리즘 과 토마토 문제

BFS(Breath-First Search, 너비 우선 탐색)

너비 우선 탐색은 그래프의 모든 정점을 방문하는 알고리즘 중 하나입니다.

현재 정점과 인접한 정점들을 하나씩 검사해 아직 방문 하지 않은 정점을 자료구조 큐에 넣습니다. 그리고 검사가 끝나면 큐의 가장 앞에 있는 점을 방문해 위의 과정을 진행하고 Pop합니다.

이 과정을 큐가 비어 있을 때까지 반복 하는 것이 BFS입니다.

 

저는 BFS 문제로 백준의 토마토 문제를 풀어 보겠습니다.

 

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

7576번: 토마토

 

저는 아래와 같은 방법으로 풀었습니다. 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point{ // 좌표와 날짜를 저장할 클래스 입니다.
	int r, c, day;
	
	Point3(int r, int c, int day) {
		this.r = r;
		this.c = c;
		this.day = day;
	}
}

class Main{
	static int[][] arr;
	static Queue<Point> q = new LinkedList<Point>(); //Point 클래스로 큐를 만듭니다.
	static int[] m_r = {1, -1, 0, 0}; // 상하 좌우로 이동하기 위한 값입니다.
	static int[] m_c = {0, 0, 1, -1};
	static int Row;
	static int Col;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		Col = scan.nextInt();
		Row = scan.nextInt();
		
		arr = new int[Row][Col];
		
		for(int r=0 ; r<Row ;r++) { //농장에 토마토의 상태를 입력 받습니다.
			for(int c=0;c<Col;c++) {
				arr[r][c] = scan.nextInt();
				if(arr[r][c] == 1) {
					Point3 temp = new Point3(r, c, 0);
					q.add(temp);
				}
					
			}
		}
		
		int res = bfs(); //bfs탐색 알고리즘 이후에
		
		for(int r=0 ; r<Row ;r++) { // 아직 안 익은게 있으면
			for(int c=0;c<Col;c++) {
				if(arr[r][c] == 0) {
					res = -1;
				}
					
			}
		}
		
		System.out.println(res); //결과 출력
	}
	
	public static int bfs() {
		int res_day=0;
		
		while(!q.isEmpty()) {
			Point here = q.remove(); //큐의 front

			int r = here.r;
			int c = here.c;
			int day = here.day;
			
			if(res_day<day) // 현재 방문 지점의 날짜가 더 이후 날짜이면
				res_day = day;
			
			for(int n=0;n<4;n++) { //상하좌우 토마토 검사
				int t_r = r + m_r[n];
				int t_c = c + m_c[n];
				
				if(check(t_r, t_c)) {
					Point there = new Point(t_r, t_c, day+1);
					arr[t_r][t_c]=1;
					q.add(there);
				}
			}
		}
		
		return res_day;
	}
	public static boolean check(int row, int col) { 
		if(row<Row && col<Col && 0<=row && 0<=col) { // 농장 안에 있는지
			if(arr[row][col] == 0) // 안익은 토마토가 맞는지
				return true;
		}	
		return false;

	}

}