백준_7576 토마토(자바) / BFS

시간 & 메모리 제한

문제

입력 & 출력

BFS를 이용한 문제풀이

package com.Back;

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

public class Back_7576 {
	static int col, row,ans=0;
	static int[][] map;
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	static Queue<point> q = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		map = new int[col][row];
		
		for (int i = 0; i < col; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < row; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
					q.add(new point(i, j, 0));
				}
			}
		}
		bfs();
		
		if(check()) {
			System.out.println(ans);
		}else {
			System.out.println(-1);
		}
	}
	private static boolean check() {
		for (int i = 0; i < col; i++) {
			for (int j = 0; j < row; j++) {
				if(map[i][j]==0) {
					return false;
				}
			}
		}
		return true;
	}
	private static void bfs() {
		while(!q.isEmpty()) {
			point temp = q.poll();
			ans=temp.day;
			for (int k = 0; k < 4; k++) {
				int xx= temp.x+dx[k];
				int yy= temp.y+dy[k];
				
				if(xx<0 || xx>=col || yy<0 || yy>=row)continue;
				if(map[xx][yy]==0) {
					map[xx][yy]=1;
					q.add(new point(xx, yy, ans+1));
				}
			}
		}
	}
	static class point{
		int x;
		int y;
		int day;
		public point(int x, int y,int day) {
			super();
			this.x = x;
			this.y = y;
			this.day=day;
		}
		
	}
}

- 이 문제는 BFS를 이용해서 문제를 해결할 수 있습니다.

 

- Step1. 입력을 받습니다. 저의 경우 for문을 두번 돌리기 싫어서 입력을 받는 동시에 BFS를 돌려야 하는 부분을 담았습니다.

 

- Step2. Class에는 지점과 그 지점에서 토마토가 익는데 걸리는 시간을 담았습니다.

 

- Step3. BFS를 만들었습니다. 이때 while에서는 사방탐색을 통해서 다음 익는 범위를 구해서 해결했습니다.

 

- Step4. 0이 있는지 확인해서 처리를 해줬습니다.