[BOJ] 7576. 토마토

BaekJoon 7576. 토마토

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

[문제 접근]

BFS 문제로 유명한 토마토

토마토가 동시다발적으로 익어가야 하기 때문에 시작 할 때 익은 토마토를 전부 큐에 넣어줬다.

넣은 토마토를 상,하,좌,우 4방향으로 검사해서 안 익은 토마토는 1로 바꿔 주고 날짜를 +1씩 해주고 큐에 넣어 준다.

while문이 끝나고 나면 박스를 전부 돌아서 토마토가 다 익었는지 확인 한다.

하나라도 안 익은 토마토가 있으면 -1, 전부 다 익었으면 마지막 큐의 날짜 값을 출력한다.

 

지난번에 풀 때는 boolean 2차배열을 이용해 좌표 값을 방문 했는지도 확인했었는데 이번에는 방문 배열을 사용하지 않았다.좌표 값이 0일 때만 방문하니깐 방문하고 나면 0에서 1로 바뀌기 때문에 굳이 방문 확인용 배열을 만들지 않아도 되는 것 같다.

 

 

 

 

 

 

 

 

 

 

 

[코드]

최근에 푼 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_75762 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt(); //가로
		int N = sc.nextInt(); //세로
		int[][] box = new int[N][M]; //상자
		int day = 0; // 날짜
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				box[i][j] = sc.nextInt();
			}
		}
		
		Queue<Cord> queue = new LinkedList<>();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (box[i][j] == 1) { //익은 토마토를 모두 큐에 저장
					queue.add(new Cord(i, j, 0));
				}
			}
		}

		while (!queue.isEmpty()) {
			Cord temp = queue.poll();
			day = temp.day;
			int[] dx = {-1, 0, 1, 0};
			int[] dy = {0, 1, 0, -1};
			
			for (int i = 0; i < 4; i++) {
				int nx = temp.x + dx[i];
				int ny = temp.y + dy[i];
				
				if (nx < N && nx >=0 && ny < M && ny >=0) {
					if (box[nx][ny] == 0) {
						box[nx][ny] = 1;
						queue.add(new Cord(nx, ny, temp.day+1));
					}
				}
			}
		}
		
		boolean flag = false; //토마토가 전부 다 익었는지 판별할 변수
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (box[i][j] == 0) { //안 익은 토마토가 있음
					flag = true;
					break;
				} else {
					continue;
				}
			}
			if (flag) {
				day = -1;
				break;
			}
		}
		System.out.println(day);
	}
	
	static class Cord{
		int x;
		int y;
		int day;
		
		public Cord(int x, int y, int day) {
			this.x = x;
			this.y = y;
			this.day = day;
		}
	}
}

 

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[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[][] map = new int[M][N];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		Queue<Cord> queue = new LinkedList<>();
		boolean[][] visited = new boolean[M][N];
		int day = 0;

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1) {
					if (visited[i][j] == true) {
						continue;
					}
					if (visited[i][j] == false) {
						queue.add(new Cord(i, j, 0));
						visited[i][j] = true;
					}
				}
			}
		};

		while (!queue.isEmpty()) {
			Cord temp = queue.poll();

			for (int k = 0; k < 4; k++) {
				int nx = temp.x + dx[k];
				int ny = temp.y + dy[k];

				if (nx>=0 && ny >=0 && nx <M && ny<N) {
					if (visited[nx][ny] == false) {
						visited[nx][ny] = true;
						if (map[nx][ny] == 0) {
							map[nx][ny] = 1;
							queue.add(new Cord(nx, ny, temp.day+1));
						}
					}
				}
			}
			day = temp.day;
		}

		boolean flag = false;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 0) {
					flag = true;
					break;
				}
			}
			if (flag) {
				day = -1;
			}

		}
		System.out.println(day);

	}
	static class Cord{
		int x;
		int y;
		int day;

		public Cord(int x, int y, int day) {
			this.x = x;
			this.y = y;
			this.day = day;
		}
	}
}