[7576]https://www.acmicpc.net/problem/7576
문제 조건
토마토를 보관하는 M×N칸의 상자에 토마토가 있다.
익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구해야 한다.
단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
문제 입력
첫 줄에는 두 정수 M,N이 주어진다. (2 ≤ M,N ≤ 1,000)
둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 들어있는 토마토의 상태가 M개의 정수로 주어진다.
1 = 익은 토마토 / 0 = 익지 않은 토마토 / -1 : 토마토가 없음
입력 예시
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1문제 풀기 전 설계
익은 토마토와 인접한 토마토들은 하루가 지나면 모두 익는다. -> BFS를 써야할 것 같은 느낌이 든다.
처음부터 익은 토마토가 2개 이상이라면 익는 날짜를 어떻게 확정할 수 있을까? -> 입력받을 때 익은 토마토를 Queue에 넣으면 된다. 그러면 Queue가 FIFO니까 BFS를 통해 나중에 저장한 토마토보다 먼저 체크를 하니 해결된다.
문제 코드
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 {
static int[][] tomatoes; // 토마토 상자(토마토의 정보를 저장할 배열)
static int[][] isVisit; // 각 토마토가 익는 날짜 및 방문 여부를 체크할 배열
static int n;
static int m;
static int[] dn = {0, 0, 1, -1}; // 토마토의 상하
static int[] dm = {1, -1, 0, 0}; // 토마토의 좌우
static Queue<int[]> queue = new LinkedList<>(); // BFS를 위한 Queue
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
m = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
tomatoes = new int[n][m];
isVisit = new int[n][m];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < m; j++) {
tomatoes[i][j] = Integer.parseInt(st.nextToken());
if (tomatoes[i][j] == 1) { // 처음부터 토마토가 익은 상태라면
queue.offer(new int[]{i, j}); // Queue에 해당 위치를 저장
isVisit[i][j] = 1; // 익은 일수에 1을 저장
}
}
}
System.out.println(bfs());
}
private static int bfs() { // 한 토마토에 인접한 모든 토마토를 탐색하고 같은 일수를 저장함 -> BFS
while (!queue.isEmpty()) {
int[] nm = queue.remove();
int x = nm[0];
int y = nm[1];
for (int i = 0; i < 4; i++) {
// 토마토의 상하좌우 탐색
int newX = x + dn[i];
int newY = y + dm[i];
if (newX >= 0 && newX < n && newY >= 0 && newY < m) { // 배열 사이즈 안에서
if (tomatoes[newX][newY] == 0 && isVisit[newX][newY] == 0) {
/* 해당 위치의 토마토가 익지 않은 상태이고 방문한 적이 없다면
익은 날짜를 +1해서 저장하고 다음 탐색을 위해 Queue에 위치 추가
*/
isVisit[newX][newY] = isVisit[x][y] + 1;
queue.offer(new int[]{newX, newY});
}
}
}
}
int days = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (isVisit[i][j] == 0 && tomatoes[i][j] != -1) { // 익지 않은 토마토가 있다면 -1 리턴
return -1;
}
else if (isVisit[i][j] > days) days = isVisit[i][j]; // 모든 날짜 중 가장 큰 값
}
}
return days - 1; // 처음부터 익은 토마토를 1일로 설정했으니 -1한 후 리턴
}
}문제 풀이
토마토의 정보를 저장할 2차원 배열 tomatoes과 방문 여부 및 익는 날짜를 저장할 isVisit을 생성하고 입력을 받아 저장한다. 익은 토마토라면 Queue에 해당 위치를 저장하고 isVisit의 해당 인덱스 값을 1로 바꿔준다.
그 후 BFS를 통해 인접 위치를 탐색하고 만약 방문하지 않았고 익지 않은 토마토라면 탐색을 시작한 날짜에 +1을 해서 isVisit 배열의 해당 토마토 인덱스에 저장한다.
탐색이 끝나면 tomatoes와 isVisit 배열을 처음부터 탐색하며 아직 익지 않은 토마토가 있으면 -1을 출력하고 그렇지 않다면 isVisit 배열의 가장 높은 값에서 1을 뺀 값을 출력한다. (처음부터 익어있던 토마토의 익은 날짜를 1로 저장했으므로)
Review
이번 문제에서는 초기 값이 1인 토마토들을 입력 받을 때 Queue에 넣어놓을 생각을 안해서 헤맸었다. 그래도 비슷한 문제를 몇 번 풀어보니 BFS와 조금은 친해진 기분이 든다. 하지만 아직도 좀 어색하기 때문에 갈길이 멀다.
