분명 이전에 토마토 문제를 풀었는데 아직 안푼문제라고 적혀있길래
이전에 푼 문제들을 찾아봤더니
이전에 푼 문제는 7569 토마토 문제였다. (같은 문제인줄 알았는데 아니더라)
이왕 문제를 본 김에 풀어보기로 했고 이전에 푼 문제보다 더 쉬워서 금방 풀었는것 같다
문제풀이
입력과 동시에 익은 토마토가 들어오면 바로 큐에 넣어준다 (익은 토마토는 여러개일수 있다)
큐에는 임의의 노드클래스를 생성해 행, 열, 현재날짜 정보를 넣어준다.
큐에 익은 토마토 노드를 다 넣었다면
moveTomato에서 큐가 다 빌때까지 상하좌우로 이동을 한다.
(상 하 좌 우 값을 더해 다음 가야할 노드정보를 구한다)
만약 다음에 가야하는 노드의 토마토 상태가 -1이거나 1이면 continue
만약 해당 노드가 이미 방문한 노드라면 continue
혹은 다음 노드 정보가 범위를 벗어난다면 다 continue로 뛰어넘는다.
익혀야하는 토마토를 발견하면 해당 토마토를 익히고 day를 증가시킨다
그리고 day의 최대값을 따로 저장한다. (전체를 수행 후 day를 가져와야해서)
토마토 익히기가 끝나고 토마토 판의 상태를 확인한다.
만약 덜익은 토마토가 하나라도 있으면 -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 B7576 {
static int N,M;
static int[][] Board;
static int[][] D = {{0,-1} , {0,1} , {-1,0} , {1,0}}; //상하좌우
static Queue<Node> queue = new LinkedList<>();
static boolean[][] visited;
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());
Board = new int[M][N];
visited = new boolean[M][N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 0; j < N; j++) {
Board[i][j] = Integer.parseInt(st.nextToken());
if(Board[i][j]==1) queue.add(new Node(i,j,0));
}
}
moveTomato();
}
private static void moveTomato() {
int res = 0;
while(!queue.isEmpty()){
Node temp = queue.remove();
// 최대값 저장 : 전체를 수행 후 day를 저장한다
if(res<temp.day) res = temp.day;
for (int i = 0; i < 4; i++) {
int nr = temp.row + D[i][0];
int nc = temp.col + D[i][1];
//해당 토마토가 익힐수 있는 토마토인지 확인하는 if문
if(nr < 0 || nc < 0 || nr >= M || nc >= N) continue;
if(visited[nr][nc]) continue;
if(Board[nr][nc]==-1) continue;
if(Board[nr][nc]==1) continue;
//익힐수 있는 토마토라면?
visited[nr][nc] = true;
Board[nr][nc] = 1;
queue.add(new Node(nr,nc, temp.day+1));
}
}
//덜익은 토마토가 있는지 확인
boolean isRipe = true;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (Board[i][j] == 0) {
isRipe = false;
break;
}
}
}
if(isRipe) System.out.println(res);
else System.out.println(-1);
}
static class Node{
int row,col,day;
Node(int r, int c, int d){
row = r;
col = c;
day = d;
}
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 11057 - 오르막 수 (0) | 2022.09.08 |
---|---|
[백준 java] 11727 - 2xn 타일링 2 (0) | 2022.09.07 |
[백준 java] 1874 - 스택 수열 (0) | 2022.09.04 |
[백준 java] 10866 - 덱 (0) | 2022.09.04 |
[java 백준] 1021 - 회전하는 큐 (0) | 2022.09.03 |