[BOJ][JAVA] 7576번 : 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

오답코드는 따로 없고 내가 실수했던 부분을 밑에서 기록하겠다.

---

오답노트(푸는 동안 사고과정 및 개선점)

이 토마토문제에서 중요한 것은 여러개의 토마토가 익을 때, 멀리 떨어져있어도 동일한 날짜에 익는다는 것이다. 처음에는 day를 큐에 안넣고 그냥 큐에 poll될때마다 하나씩 늘렸는데, 이러면 똑같은 날짜에 익기 시작해야되는 토마토가 다른 날짜에 익어버린다. 

 

day를 큐에 넣고 같이 관리해서 이건 day보다 하나씩 더 많게 해야 큐에서 올바르게 날짜관리가 된다. 인구이동 문제랑 비슷한 맥락이 있다고 느꼈다.

---

정답코드

java

접기

import java.util.*;
import java.io.*;
 
public class Main {
	static int n;
	static int m;
	static int[] di = { -1, 0, 1, 0 };
	static int[] dj = { 0, 1, 0, -1 };
 
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][m];
		LinkedList<int[]> q = new LinkedList();
		int tomatos = 0;
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					q.add(new int[] { i, j, 0 });
				}
				if (map[i][j] == 0) {
					tomatos++;
				}
			}
		}
		int day = 0;
		while (!q.isEmpty()) {
			int[] cur = q.pollFirst();
			day = cur[2];
			for (int i = 0; i < 4; i++) {
				int ni = di[i] + cur[0];
				int nj = dj[i] + cur[1];
				if (ni < n && nj < m && ni >= 0 && nj >= 0) {
					if (map[ni][nj] == 0) {
						map[ni][nj] = 1;
						q.add(new int[] { ni, nj, day + 1 });
					}
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(map[i][j]== 0) {
					System.out.println(-1);
					return;
				}
			}
		}
 
		System.out.println(day);
 
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^