728x90
문제
상자에 익은 토마토와 덜 익은 토마토, 빈 공간이 존재할 때
익은 토마토의 주변 한 칸 내에 있는 덜 익은 토마토들은
하루가 지날 때마다 영향을 받아 익는다.
이때 상자 안에 존재하는 모든 토마토가 익기 위해서는
최소 며칠이 걸리는지 출력하라. (모두 익을 수 없는 경우에는 -1)
접근 방식
익은 토마토가 여러 곳에 존재하는 경우에는 각각의 익은 토마토에서
매일 상하좌우 칸의 덜 익은 토마토를 1로 바꿔줘야 한다.
이전에 풀었던 최단 거리 문제와 비슷한 방식으로 풀 수 있는 문제지만
출발지가 여러 개라는 조건이 추가된 문제다.
1926번 + 2176번 문제가 합쳐진 경우로
모든 출발지를 찾은 후에 큐에 넣고 BFS 알고리즘을 적용하면서
상하좌우에 거리를 1씩 늘려주면 된다.
이번 문제에서 거리는 날짜라고 볼 수 있다는 것이 포인트로
모든 열매가 다 익었을 때의 날짜를 출력하거나
큐를 다 돌았는데도 익지 않은 열매가 존재한다면 -1을 출력하면 된다.
풀이
public class Main {
private static int[] dx = {1, 0, -1, 0};
private static int[] dy = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[][] tomato = new int[n][m];
Queue<Pair> queue = new ArrayDeque<>();
int[][] day = new int[n][m];
int target = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < m; j++) {
int t = Integer.parseInt(st.nextToken());
tomato[i][j] = t;
if (t == 1) {
queue.offer(new Pair(i, j));
day[i][j] = 1;
} else if (t == 0) {
target++;
}
}
}
if (target == 0) {
System.out.println(0);
return;
}
while (!queue.isEmpty()) {
Pair cur = queue.poll();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (day[nx][ny] > 0 || tomato[nx][ny] == -1) continue;
target--;
if (target == 0) {
System.out.println(day[cur.x][cur.y]);
return;
}
day[nx][ny] = day[cur.x][cur.y] + 1;
queue.offer(new Pair(nx, ny));
}
}
System.out.println(-1);
}
private static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 1697번 : 숨바꼭질 (0) | 2023.10.11 |
---|---|
[백준] 4179번 : 불! (0) | 2023.10.10 |
[백준] 2178번 : 미로 탐색 (0) | 2023.10.09 |
[BFS] 구현 및 팁 (1) | 2023.10.09 |
[백준] 1926번 : 그림 (1) | 2023.10.09 |