[백준/7576/Java] 토마토 - BFS 풀이

문제

www.acmicpc.net/problem/7576

7576번: 토마토

 

 

 

 

문제를 먼저 풀고 오신 다음에 풀이를 보시는 것을 추천드립니다.

이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

이 글은 BFS 알고리즘으로 2차원 배열을 사용해서 푸는 것을 알아보는 글이라서 BFS로 풀어보겠습니다.

문제분석

하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익습니다.

인접한 곳은 왼쪽, 오른쪽, 앞(위), 뒤(아래) 네 방향에 있는 토마토입니다. 대각선은 영향을 주지 않습니다.

즉, 인접한 토마토가 없고 한 칸 이상 떨어져있다면 그 토마토는 익을 수 없습니다.

모든 토마토가 익는 최소일수를 구하는 문제입니다.

 

입력

첫번째 줄은 M, N 정수를 입력받습니다.

  M은 상자의 가로칸 수, N은 상자의 세로 칸 수. 단, 2 <= M,N <= 1,000

2번째 줄부터 N개의 줄에 상자에 담긴 토마토의 정보가 주어집니다.

  - 정수 1 : 익은 토마토

  - 정수 0 : 익지 않은 토마토

  - 정수 -1 : 토마토가 들어있지 않은 칸

 

 

출력

토마토가 모두 익을 때까지의 최소 날짜를 출력해야 합니다.

처음부터 모든 토마토가 익어있는 상태이면 0을 출력합니다.

토마토가 모두 익지 못 하는 상황이면 -1을 출력합니다.

 

풀이

먼저 3X3 박스에 가장 우측 밑에 익은 토마토 1개가 있고 그 외 칸에 익지 않은 토마토가 있다고 할 때 전체를 퍼지는 것을 확인해보겠습니다.

그와 동시에 동일하게 3X3 배열을 만들고 거기에 인접한 토마토가 익을 때마다 동일한 위치에 날짜를 표시하겠습니다.

마지막에 날짜 배열에서 가장 큰 값이 토마토가 익는 최소 날짜가 됩니다. 물론, 모든 토마토가 익는 경우에만 한정됩니다.

 

0일째

익은 토마토는 가장 우측 아래에 있고 날짜를 표시하는 배열에 0을 저장합니다.

물론 그 외 모든 칸도 날짜는 모두 0입니다.

 

1일째

인접한 토마토를 익게 만듭니다. 왼쪽, 위쪽으로만 이동할 수 있습니다.

따라서, 상자와 날짜 배열에 각각 1을 설정합니다.

 

2일째

인접한 토마토를 익게 만듭니다. 왼쪽, 위쪽으로만 이동할 수 있습니다.

따라서, 상자 배열에서 인접한 토마토를 1로 변경합니다.

그리고 날짜 배열에 동일한 위치에 기존 날짜에서 1을 더한 값 2를 저장합니다.

 

 

3일째

인접한 토마토를 익게 만듭니다. 왼쪽, 위쪽으로만 이동할 수 있습니다.

따라서, 상자 배열에서 인접한 토마토를 1로 변경합니다.

그리고 날짜 배열에 동일한 위치에 기존 날짜에서 1을 더한 값 3을 저장합니다.

 

 

4일째

인접한 토마토를 익게 만듭니다. 마지막 남은 칸에 있는 토마토가 익습니다.

따라서, 상자 배열에서 인접한 토마토를 1로 변경합니다.

그리고 날짜 배열에 동일한 위치에 기존 날짜에서 1을 더한 값 4를 저장합니다.

 

 

상자 배열을 전부 체크해서 모두 1이면 모든 토마토가 익었으므로 날짜 배열에서 모든 값을 체크해서 가장 큰 값을 찾아서 출력하면 됩니다.

 

이 문제와 같이 동일한 크기의 배열을 2개 선언하고 하나는 문제에서 주어진 값, 다른 하나는 문제를 풀기 위한 값을 저장하면서 이동하는 BFS, DFS, 나아가 DP(Dynamic Programming) 문제들도 있으니 이렇게 푸는 방식에 익숙해지시면 좋습니다.

 

예제풀이

백준온라인에 나온 예제들을 상자/날짜 배열을 모두 출력해서 어떻게 이동하는지 보겠습니다.

 

Input#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

Output#1

우측 아래부터 좌측 위까지 모두 이동하였고 8일이 소요되었습니다.

8

// 상자배열
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]

// 날짜배열
[8, 7, 6, 5, 4, 3]
[7, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
[5, 4, 3, 2, 1, 0]

 

Input#2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

 

Output#2

좌측 위에 혼자 외로이 있는 토마토가 있어서 모든 토마토가 익지 못 하였습니다.

상자배열에서 0이 하나라도 나오면 안 익은 토마토가 있다는 뜻이므로 -1을 출력하면 됩니다.

-1

// 상자배열
[0, -1, 1, 1, 1, 1]
[-1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1]

// 날짜배열
[0, 0, 6, 5, 4, 3]
[0, 6, 5, 4, 3, 2]
[6, 5, 4, 3, 2, 1]
[5, 4, 3, 2, 1, 0]

 

Input#3

문제 있는 예제 3번과 4번은 비슷한 면이 있어서 4번 예제만 넣어보겠습니다.

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

 

Output#3

익은 토마토가 일렬로 되어 있어서 끝까지 따라가서 14일이 소요되었습니다.

14

// 상자배열
[-1, 1, 1, 1, 1]
[1, -1, -1, -1, 1]
[1, -1, -1, -1, 1]
[1, -1, -1, -1, 1]
[1, 1, 1, 1, 1]

// 날짜배열
[0, 0, 1, 2, 3]
[14, 0, 0, 0, 4]
[13, 0, 0, 0, 5]
[12, 0, 0, 0, 6]
[11, 10, 9, 8, 7]

 

Input#4

마지막 예제인데 생각보다 이렇게 넣으면 틀리는 사람들이 종종 있었습니다.

2 2
1 -1
-1 1

 

Output#4

상하좌우로 이동할 수 없지만 이미 모두 익어있는 토마토라서 0을 출력해야 합니다.

0

// 상자배열
[1, -1]
[-1, 1]

// 날짜배열
[0, 0]
[0, 0]

 

소스 (객체 사용)

지금까지 설명 안 한 부분이 있는데 BFS 알고리즘에서 사용해야 하는 Queue에 값을 어떻게 넣는가 입니다.

배열의 i, j 위치를 저장하고 Node 객체에 설정해서 Queue에 넣었습니다.

객체로 하면 나중에 정렬하기도 편해서 저는 객체를 주로 사용하고 있습니다.

 

 

결과값을 출력하고 println 구문들이 주석처리되어 있는데 제가 위에서 보여드린 상자/날짜 배열을 확인하기 위하여 출력한 소스입니다.

상자/날짜 배열을 확인하고 싶으신 분들은 주석해제하고 돌려보시기 바랍니다.

주석을 풀은 상태에서 백준 온라인에 제출하시면 아마도 결과값이 많다고 나올 겁니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int M;
	static int d[][];

	static int v[][];

	static int Answer;

	static Queue<Node> queue = new LinkedList<Node>();

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

		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		M = Integer.valueOf(st.nextToken());
		N = Integer.valueOf(st.nextToken());

		d = new int[N][M];
		v = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				d[i][j] = Integer.valueOf(st.nextToken());
				if (d[i][j] == 1) {
					Node node = new Node(i, j);
					queue.offer(node);
				}
			}
		}

		bfs();

		check();

		System.out.println(Answer);

//		System.out.println("\n// 상자배열");
//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(d[i]));
//		}
//		System.out.println();
//
//		System.out.println("// 날짜배열");
//		for (int i = 0; i < N; i++) {
//			System.out.println(Arrays.toString(v[i]));
//		}
	}

	private static void check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (v[i][j] == 0 && d[i][j] == 0) {
					Answer = -1;
					return;
				} else {
					Answer = Math.max(Answer, v[i][j]);
				}
			}
		}
	}

	private static void bfs() {
		int i = 0;
		int j = 0;
		Node node = null;
		while (queue.isEmpty() == false) {
			node = queue.poll();
			i = node.x;
			j = node.y;

			d[i][j] = 1;

			if (i > 0 && d[i - 1][j] == 0 && v[i - 1][j] == 0) {
				v[i - 1][j] = v[i][j] + 1;
				Node next = new Node(i - 1, j);
				queue.offer(next); // 상
			}
			if (i < N - 1 && d[i + 1][j] == 0 && v[i + 1][j] == 0) {
				v[i + 1][j] = v[i][j] + 1;
				Node next = new Node(i + 1, j);
				queue.offer(next); // 하
			}
			if (j > 0 && d[i][j - 1] == 0 && v[i][j - 1] == 0) {
				v[i][j - 1] = v[i][j] + 1;
				Node next = new Node(i, j - 1);
				queue.offer(next); // 좌
			}
			if (j < M - 1 && d[i][j + 1] == 0 && v[i][j + 1] == 0) {
				v[i][j + 1] = v[i][j] + 1;
				Node next = new Node(i, j + 1);
				queue.offer(next); // 우
			}
		}
	}
}

class Node {
	int x;
	int y;

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

 

다른 소스 (좌표 저장)

다른 소스를 하나 더 보여드리겠습니다.

Queue에 넣을 때 i, j 위치를 객체 사용없이 저장하는 방법입니다.

N, M 값이 크지 않을 때 사용가능한 방법입니다.

i와 j를 하나의 숫자로 만들어서 저장하는 방법으로 i에 1001을 곱하고 j를 더해서 저장합니다.

대신 꺼낼 때는 이를 거꾸로 계산해야 하므로 i는 1001을 나누고, j는 1001 나머지를 구하는 방법입니다.

queue.offer(i * 1001 + j);

int pos = queue.poll();
int i = pos / 1001;
int j = pos % 1001;

 

좌표 값을 저장해서 풀은 소스입니다.

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

public class Main
{
	static int N;
	static int M;
	static int d[][];

	static int v[][];

	static int Answer;

	public static void main(String[] args) throws Exception
	{
		Scanner sc = new Scanner(System.in);

		M = sc.nextInt();
		N = sc.nextInt();

		d = new int[N][M];
		v = new int[N][M];

		Queue<Integer> queue = new LinkedList<Integer>();

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				d[i][j] = sc.nextInt();
				if (d[i][j] == 1)
				{
					queue.offer(i * 1001 + j);
				}
			}
		}

		if (queue.isEmpty() == false)
		{
			bfs(queue);

			check();
		}

		System.out.println(Answer);

		// for (int i = 0; i < N; i++)
		// {
		// System.out.println(Arrays.toString(d[i]));
		// }
		// System.out.println();
		//
		// for (int i = 0; i < N; i++)
		// {
		// System.out.println(Arrays.toString(v[i]));
		// }
	}

	private static void bfs(Queue<Integer> queue)
	{
		int i = 0;
		int j = 0;
		int pos = 0;
		while (queue.isEmpty() == false)
		{
			pos = queue.poll();
			i = pos / 1001;
			j = pos % 1001;

			d[i][j] = 1;

			if (i > 0 && d[i - 1][j] == 0 && v[i - 1][j] == 0)
			{
				v[i - 1][j] = v[i][j] + 1;
				queue.offer((i - 1) * 1001 + j); // 상
			}
			if (i < N - 1 && d[i + 1][j] == 0 && v[i + 1][j] == 0)
			{
				v[i + 1][j] = v[i][j] + 1;
				queue.offer((i + 1) * 1001 + j); // 하
			}
			if (j > 0 && d[i][j - 1] == 0 && v[i][j - 1] == 0)
			{
				v[i][j - 1] = v[i][j] + 1;
				queue.offer(i * 1001 + (j - 1)); // 좌
			}
			if (j < M - 1 && d[i][j + 1] == 0 && v[i][j + 1] == 0)
			{
				v[i][j + 1] = v[i][j] + 1;
				queue.offer(i * 1001 + (j + 1)); // 우
			}
		}
	}
	
	private static void check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (v[i][j] == 0 && d[i][j] == 0) {
					Answer = -1;
					return;
				} else {
					Answer = Math.max(Answer, v[i][j]);
				}
			}
		}
	}
}

 

관련글:

2021/01/21 - [Algorithm] - [백준/BOJ/1697] 숨바꼭질 - BFS 풀이

[백준/BOJ/1697] 숨바꼭질 - BFS 풀이

 

2021/01/29 - [Algorithm] - [백준/BOJ/2178] 미로탐색 - BFS 풀이

[백준/BOJ/2178] 미로탐색 - BFS 풀이

 

 

2020/12/10 - [Algorithm] - [알고리즘] 백준 온라인 저지 사이트 소개

[알고리즘] 백준 온라인 저지 사이트 소개