백준 7576번 java 풀이 - bfs

반응형

풀이

이 문제는 여러 토마토가 동시에 익어가기 때문에 bfs 알고리즘을 통해 풀어야 합니다.

큐 자료구조에 토마토의 좌표값을 넣었기 때문에 Point 라이브러리를 사용하여 좌표값을 넣었습니다.

http://cris.joongbu.ac.kr/course/java/api/java/awt/Point.html

Point (Java 2 Platform SE 5.0)

array배열엔 해당 인덱스까지 소요된 시간을 저장하고 visit 배열엔 해당 인덱스를 방문했는지 유무를 boolean으로 저장했습니다.

bfs 알고리즘을 다 수행한 뒤 array배열에 저장된 최대 소요시간을 출력해야 하기 때문에 이중 반복문으로 max값을 찾았고 익지 않은 토마토(배열값 0)가 발견되면 이중 반복문을 나오기 위해 Loop: 를 사용했습니다.

https://ifuwanna.tistory.com/269

[Java] 중첩 반복문 break ( 이중 for문 break )

import java.util.*;
import java.io.*;
import java.awt.Point;

class Main{
	static int[][] array;
	static boolean[][] visit;
	static int row = 0;
	static int col = 0;
	static Queue<Point> queue = new LinkedList<Point>();
	public static void main(String[] args) throws java.lang.Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		col = Integer.parseInt(st.nextToken());
		row = Integer.parseInt(st.nextToken());
		array = new int[row][col];
		visit = new boolean[row][col];
		
		for(int i=0; i<row; i++){
			st = new StringTokenizer(br.readLine());
			int j=0;
			while(st.hasMoreTokens()){
				array[i][j] = Integer.parseInt(st.nextToken());
				if(array[i][j] == 1){
					queue.add(new Point(j,i));
					visit[i][j] = true;
				}
				j++;
			}
		}
		
        if(!queue.isEmpty()){
		    Point p = queue.poll();
		    bfs(p.x,p.y);
        }
		
		int max = 0;
		Loop1:
		for(int i=0; i<row; i++){
			for(int j=0; j<col; j++){
				if(array[i][j] > max)
					max = array[i][j];
				else if(array[i][j] == 0){
					max = 0;
					break Loop1;
				}
			}
		}
		System.out.println(max - 1);
	}
	
	public static void bfs(int x, int y){
		if(x > 0 && array[y][x-1] != -1 && visit[y][x-1] == false){//왼쪽 검사
			queue.add(new Point(x-1,y));
			visit[y][x-1] = true;
			array[y][x-1] = array[y][x] + 1;
		}
		if(x+1 < col && array[y][x+1] != -1 && visit[y][x+1] == false){//오른쪽 검사
			queue.add(new Point(x+1,y));
			visit[y][x+1] = true;
			array[y][x+1] = array[y][x] + 1;
		}
		if(y > 0 && array[y-1][x] != -1 && visit[y-1][x] == false){//위 검사
			queue.add(new Point(x,y-1));
			visit[y-1][x] = true;
			array[y-1][x] = array[y][x] + 1;
		}
		if(y+1 < row && array[y+1][x] != -1 && visit[y+1][x] == false){//위 검사
			queue.add(new Point(x,y+1));
			visit[y+1][x] = true;
			array[y+1][x] = array[y][x] + 1;
		}
		
		if(!queue.isEmpty()){
			Point p = queue.poll();
			bfs(p.x,p.y);
		}
	}
}