○ 문제 요약
익지 않은 토마토들은 상, 하, 좌, 우에 익은 토마토의 영향을 받아 익게 된다. 상자에 있는 토마토가 모두 익은 토마토가 되려면 며칠이 지나야 하는지 출력해라.
○ 문제 풀이
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 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()) ;
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][M];
for(int i = 0 ; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0 ; j < M; j++){
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
bfs(arr,M,N);
}
static void bfs(int[][] arr, int M, int N){
int[] dr = {-1,1,0,0};
int[] dc = {0,0,-1,1};
Queue<Dot> que = new LinkedList<>();
int day = 0 ;
for(int i = 0 ; i < N; i++){
for(int j = 0 ; j < M ; j++){
if(arr[i][j] == 1){
que.offer(new Dot(i,j,0));
}
}
}
while(!que.isEmpty()){
Dot dot = que.poll();
day = dot.day;
for(int i = 0 ; i < 4; i++){
int nx = dot.x + dr[i];
int ny = dot.y + dc[i];
if(nx >= 0 && N > nx && ny >= 0 && M > ny ){
if(arr[nx][ny] == 0){
arr[nx][ny] = 1;
que.offer(new Dot(nx,ny,day+1));
}
}
}
}
if(check(arr,M,N)){
System.out.println(day);
}else{
System.out.println(-1);
}
}
// 모든 토마토가 익었는지 확인....
static boolean check(int[][] arr,int M, int N){
for(int i = 0 ; i < N; i++ ){
for(int j = 0 ; j < M ; j++){
if(arr[i][j] == 0){
return false;
}
}
}
return true;
}
static class Dot{
int x;
int y;
int day;
public Dot(int x, int y, int day){
this.x = x;
this.y = y;
this.day = day;
}
}
}
DFS와 BFS를 이용해서 여러 문제를 풀어보면서 풀이가 비슷하다는 느낌을 받았다. ( 아마 비슷한 문제가 풀어서 그런가?)
이 문제도 이전에 풀은 문제와 별로 다르지 않다고 느껴졌다. 하지만 이번에는 클래스를 하나 만들어서 문제를 풀어보았다. 다른 사람들의 풀이를 보면 클래스를 활용해서 문제를 푸는 사람들이 있었는데 여러 방법을 사용해서 문제를 풀면 자바에 대한 숙련도도 높아질 거라는 생각이 들었다.
각설하고 이 문제를 풀면서 중요하다고 생각되는 부분을 말하고 싶다. 먼저 너비 우선 방식으로 문제를 풀기 때문에 Queue를 만들어주고 토마토의 위치를 넣은 배열에 익은 토마토가 있는 좌표를 Queue에 넣어준다.
그 좌표를 기준으로 상, 하, 좌, 우에 있는 토마토들이 익은 토마토인지 익지 않은 토마토인지 확인을 해서 익지 않은 토마토이면 익은 토마토로 바꿔주고 바꾼 토마토의 좌표를 Queue에 다시 넣어서 이 과정을 반복한다.
과정을 반복한 후 check() 메서드를 통해 익지 않은 토마토가 있는지 확인하고 익지 않은 토마토가 있다면 -1을 출력하도록 하고 익지 않은 토마토가 없다면 모든 토마토가 익는데 걸린 일수를 출력해준다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 10816. 숫자 카드2 (JAVA) (0) | 2022.05.17 |
---|---|
백준 1920. 수 찾기(JAVA) (0) | 2022.05.16 |
백준 2178. 미로 탐색(JAVA) (0) | 2022.04.20 |
백준 9372. 상근이의 여행(JAVA) (0) | 2022.04.18 |
백준 11725. 트리의 부모 찾기 (0) | 2022.04.11 |