[문제] 백준 7576번 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

내 풀이

 

익은 토마토를 기준으로 상하좌우의 안익은 토마토가 익는 것이므로,

큐에 익은 토마토의 좌표를 넣었다.

 

그리고 익은 토마토가 걸리는 기간을 따로 저장하는 visited 배열을 만들었다.

익지 않은 토마토에 대해서는 visited 배열의 값이 -1을 갖도록 했다.

 

큐에 있는 익은 토마토의 위치를 기준으로 4방 탐색하면서 안익은 토마토를 기준으로 계속해서 큐에 넣어줬다.

 

public class BOJ_7576 {
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	static int N, M;
	static int[][] matrix;
	static Queue<int[]> q = new LinkedList<>(); // 익은 토마토: 좌표 넣기
	static int[][] visited; // 소요되는 요일 담기 & 방문 체크

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		M = Integer.parseInt(st.nextToken()); // 가로칸 수
		N = Integer.parseInt(st.nextToken()); // 세로칸 수
		matrix = new int[N][M];
		visited = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int tmp = Integer.parseInt(st.nextToken());
				matrix[i][j] = tmp;
				if (tmp == 1) { // 익은 토마토에 대하여
					q.offer(new int[] { i, j }); // 큐에 삽입
					visited[i][j] = 0; // 소요날짜 0
				}
				if (tmp == 0) // 안익은 토마토
					visited[i][j] = -1; // 아직 안익은거 표시
			}
		}

		while (!q.isEmpty()) {
			int[] current = q.poll();
			
			int x = current[0];	//현재 좌표
			int y = current[1];
			int day = visited[current[0]][current[1]];	// 현재토마토가 익는데 소요된 기간
			
			// 상하좌우 탐색
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx>=0 && nx<N && ny>=0 && ny<M) {
					// 안익은 토마토에 대하여
					if(visited[nx][ny] == -1 && matrix[nx][ny] == 0) {
						visited[nx][ny] = day+1;
						q.offer(new int[] {nx,ny});
					}
				}
			}
		}
		//토마토가 익는 날 구하기
		int ans = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(visited[i][j] == -1) {	// 안 익은게 있음
					System.out.println(-1);
					return;
				}
				ans = Math.max(visited[i][j], ans);
			}
		}
		System.out.println(ans);
	}

}

풀이 2

public class BOJ_7576 {
	static int N,M, map[][];
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	static Queue<int[]> tomato = new LinkedList<>();
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
	
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		// init map
		map = new int[N][M];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(in.readLine()," ");
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
					tomato.offer(new int[] {i,j,0});	// 0: 토마토가 익는 날짜
				}
			}
		}
		int time = 0;
		boolean[][] visited = new boolean[N][M];
		if(isFullyRiped()) {
			System.out.println(0);
			return;
		}
		while(!tomato.isEmpty()) {
			int[] curr = tomato.poll();
			time = curr[2];	// time을 계속 갱신시켜준다. 
            //(가장 마지막에 익은 토마토가 곧 총 토마토가 익는 시간)
		
        	for(int d=0;d<4;d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];
                // 아직 방문하지 않았고, 안익은 토마토에 대해
				if(nr>=0 && nr<N && nc>=0 && nc<M && !visited[nr][nc] && map[nr][nc]==0) {
					map[nr][nc]=1;	// 토마토 익은 처리
					visited[nr][nc] = true;	// 방문 처리
					tomato.offer(new int[] {nr,nc, curr[2]+1});	
                    //하루 더 소요되므로 curr[2]+1
				}
			}
		}
		if(!isFullyRiped()) time = -1;	// 다 안익었으면 -1
		System.out.println(time);
	}
static boolean isFullyRiped() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==0) return false;
			}
		}
		return true;
	}
}

dfs로 풀려고 했는데, 시간을 갱신 못하겠더라,,