(Java) 백준 7576 - 토마토
전형적인 BFS 문제라고 생각했다.
그러나 푸는데 정말 시간이 오래 걸렸다.
처음에는 입력값을 배열에 넣고 1을 발견할 때마다 bfs를 실행시키려고 했다.
그런데 밑에 테스트 케이스를 만나면 6이 아닌 9를 반환하게 된다.
6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1문제에서 요구하는 방향은 모든 익은 토마토에서 하루가 지날 때마다 주변에 토마토가 익는 방식인데
나는 첫번째 익은 토마토를 발견하면 bfs를 실행시키고 또 다른 익은 토마토를 발견하면 또 bfs를 실행시켜
결국 똑같은 값이 두 번 출력되는 것이었다.
그래서 bfs에 넘기는 입력값을 List<int[]>로 설정해 모든 익은 토마토 인덱스를 한 번에 bfs 메서드에 넘겨주었다.
큐에 모든 익은 토마토의 인덱스를 넣으면 문제가 원하는 방향으로 해결할 수 있을 것이라고 생각했다.
실행 순서는 다음과 같다.
1. 입력값을 배열에 삽입한다.
2. 배열에서 익은 토마토를 발견하면 배열 형태로 List에 저장한다.
3. bfs메서드에 List<int[]>를 입력값으로 넘겨준다.
4. List의 모든 원소를 뽑아 배열 형태로 queue에 삽입한다.
5. bfs를 실행한다.
6. 완성된 배열을 탐색하면서 0을 발견하면 토마토가 모두 익지 못하는 상황이므로 -1을 반환한다.
7. 탐색한 배열의 값 중 가장 큰 값에 1을 빼주고 반환한다.
8. 반환 값을 출력한다.
이중 for문을 세 번이나 사용하기 때문에 시간 초과에 걸리지 않을까 생각했는데 다행히도 통과했다.
다른 분들의 풀이를 보니 이 방식보다는 익은 토마토를 먼저 queue에 삽입해서 처리하는 방식으로 풀이한 것 같다.
생각해보지 못한 방식이어서 다시 풀어볼 계획이다.
최종 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int m, n;
static int[][] arr;
static boolean[][] visited;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, 1, -1};
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[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());
}
}
// 배열에서 익은 토마토(1)을 발견하면 List에 배열 형태로 추가
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1) {
list.add(new int[]{i, j});
}
}
}
// bfs 실행후 출력
System.out.println(bfs(list));
}
static int bfs(List<int[]> list) {
// 배열에서 탐색한 최댓값을 반환하기 위한 변수
int max = 0;
Queue<int[]> queue = new LinkedList<>();
// List에서 배열을 뽑아 queue에 삽입
for (int i = 0; i < list.size(); i++) {
queue.add(list.get(i));
}
// bfs 실행
while (!queue.isEmpty()) {
int[] temp = queue.poll();
int nowX = temp[0];
int nowY = temp[1];
visited[nowX][nowY] = true;
for (int i = 0; i < 4; i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
// 탐색 범위를 벗어나면
if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m) {
continue;
}
// 방문한 노드거나 값이 -1, 0 이면
if (visited[nextX][nextY] || arr[nextX][nextY] == -1 || arr[nextX][nextY] == 1) {
continue;
}
queue.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
arr[nextX][nextY] = arr[nowX][nowY] + 1;
}
}
// 완성된 배열을 탐색
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 배열 값중 0이 있다면
if (arr[i][j] == 0) {
return -1;
} else {
// 탐색값중 가장 큰 값을 max에 배정
max = Math.max(arr[i][j], max);
}
}
}
// 하루를 빼줘야 함
return max - 1;
}
}