[Baekjoon] 백준 7576 토마토 (G5^ / BFS) - Java

링크

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

7576번: 토마토

 

 

 

문제 해석

1 : 익은 토마토

0 : 익지 않은 토마토

-1 : 빈 칸 (벽)

 

익은 토마토는 인접한 토마토에 영향을 미침

 

토마토들이 모두 익는데 걸리는 시간을 구하기

단, 익지 못하는 토마토가 있다면 -1을 결과로 출력

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {

	static int[][] map;
	static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { -1, 0, 1, 0 };
	static int max = 0;

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

		int M = Integer.parseInt(st.nextToken()); // 가로
		int N = Integer.parseInt(st.nextToken()); // 세로

		map = new int[N][M];

		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());
			}
		}

		bfs();

		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(max);

	}

	static class Point {
		int x;
		int y;
		int level;

		public Point(int x, int y, int level) {
			this.x = x;
			this.y = y;
			this.level = level;
		}

	}

	private static void bfs() {
		Queue<Point> q = new LinkedList<>();

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				if (map[i][j] == 1) {
					q.offer(new Point(i, j, 0));
				}
			}
		}

		while (!q.isEmpty()) {
			Point p = q.poll();

			for (int i = 0; i < dx.length; i++) {
				int cx = p.x + dx[i];
				int cy = p.y + dy[i];

				if (cx >= 0 && cx < map.length && cy >= 0 && cy < map[0].length 
						&& map[cx][cy] == 0) {
					map[cx][cy] = 1;
					q.offer(new Point(cx, cy, p.level + 1));
					max = Math.max(p.level + 1, max);
				}
			}
		}
	}
}

 

 

 

코드 해석

BFS문제 중 시간(Level)을 구하는 문제입니다.

 

Queue에 들어가는 Point에 level을 저장하는 멤버를 추가로 구현합니다.

 

level은 시작점 노드에서 0부터 시작하며, 탐색 도중 새로운 노드가 발견되면 새로운 노드를 찾은 기존 노드의 level + 1로 설정합니다.

 

 

추가적으로 해당 문제는 지도에 동시에 시작해야 할 시작점이 하나 이상(1이 여러개 존재 가능)인 문제입니다.

 

기존 문제(덩어리 개수 찾기)는 맵을 탐색하다 시작점을 찾으면 시작점을 q에 넣고 바로 bfs를 시작하였지만, 이번 문제는 전체 map을 모두 탐색하면서 모든 시작점을 찾아 q에 넣은 후 시작을 진행해야 합니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice