백준 7569번: 토마토

문제

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

7569번: 토마토

---

풀이

익은 토마토는 앞, 뒤, 왼쪽, 오른쪽, 위, 아래 여섯 방향에 인접해있는 익지 않은 토마토를 하루가 지나면 익게 만들 수 있을 때 모두 익을 때까지 최소 날짜를 구하는 문제입니다. 지난번에 풀었던 다른 토마토 문제의 풀이와 유사합니다.

---

코드

자바

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.LinkedList;

class point {
    int x, y, z;

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

public class Main {

    static int n, m, h, max = 1;
    static int[][][] arr;
    static ArrayList<point> list;

    public static void bfs() { // (2)
        Queue<point> queue = new LinkedList<>();
        for (point p : list) {
            queue.offer(p);
        }
        int[] dx = { -1, 0, 1, 0, 0, 0 };
        int[] dy = { 0, -1, 0, 1, 0, 0 };
        int[] dz = { 0, 0, 0, 0, -1, 1 };
        while (!queue.isEmpty()) {
            point p = queue.poll();
            max = Math.max(max, arr[p.z][p.x][p.y]); // (3)
            for (int i = 0; i < 6; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                int nz = p.z + dz[i];
                if (0 <= nx && nx < m && 0 <= ny && ny < n && 0 <= nz && nz < h && arr[nz][nx][ny] == 0) { // (4)
                    arr[nz][nx][ny] = arr[p.z][p.x][p.y] + 1;
                    queue.offer(new point(nz, nx, ny));
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        arr = new int[h][m][n];
        list = new ArrayList<>();
        for (int k = 0; k < h; k++) {
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < n; j++) {
                    arr[k][i][j] = Integer.parseInt(st.nextToken());
                    if (arr[k][i][j] == 1) list.add(new point(k, i, j)); // (1)
                }
            }
        }
        bfs();
        for (int k = 0; k < h; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (arr[k][i][j] == 0) { // (5)
                        System.out.println(-1);
                        System.exit(0);
                    }
                }
            }
        }
        System.out.println(max - 1);
    }
}

3차원 배열 arr는 처음에는 해당 위치의 토마토가 익었는지 여부를 나타냅니다.

 

(1) Arraylist list에는 최초에 익은 토마토가 있는 위치가 들어있습니다.

입력이 들어올 때 해당 위치의 토마토가 익은 상태라면 list에 추가합니다. 이후 bfs 함수로 들어갑니다.

bfs 함수 안에서 Queue는 익은 토마토의 위치 값(z, x, y)이 들어갑니다.

 

(2) bfs 함수 안에서 큐에 list의 모든 위치 값을 넣어줍니다.

이후 while문 안에서 큐가 비어있지 않을 때까지 (3)부터 (4) 과정을 반복합니다.

 

(3) max 값과 현재 탐색 중인 토마토가 익을 때까지 걸린 날짜를 비교해서 어떤 토마토가 익을 때까지 걸린 날짜의 최댓값을 구합니다.

이때 bfs 함수 내부에서의 arr는 해당 위치의 토마토가 익을 때까지 걸린 날짜 + 1을 의미하기 때문에 큐에서 poll한 위치 값을 p라고 할 때 arr[p.z][p.x][p.y]와 비교합니다.

 

(4) 그다음 탐색 위치(nz, nx, ny)가 가능한 위치이며 해당 위치의 토마토가 익었는지 여부를 확인합니다.

익지 않았다면 현재 토마토에 의하여 다음날 익을 예정이므로 arr[nz][nx][ny]에 arr[p.z][p.x][p.y] + 1을 넣어준 뒤에 (nz, nx, ny)를 큐에 삽입합니다.

 

(5) bfs 함수가 종료되면 익지 않은 토마토가 있는지 확인합니다.

익지 않은 토마토가 1개라도 있으면 문제 조건에 맞지 않으므로 -1을 출력한 후에 프로그램을 종료하고 1개도 없다면 max 값에 1을 뺀 값을 출력하고 프로그램을 종료합니다.

C언어

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
int n, m, h, max = 1, ***arr;
typedef struct {
	int x, y, z;
} Point;
typedef struct node {
	Point point;
	struct node* next;
} node;
typedef struct Queue {
	node* front;
	node* rear;
	int count;
} Queue;
void initQueue(Queue* queue) {
	queue->front = queue->rear = NULL;
	queue->count = 0;
}
void push(Queue* queue, int z, int x, int y) {
	node* now = (node*)malloc(sizeof(node));
	now->point.z = z;
	now->point.x = x;
	now->point.y = y;
	now->next = NULL;
	if (queue->count == 0) {
		queue->front = now;
	}
	else {
		queue->rear->next = now;
	}
	queue->rear = now;
	queue->count++;
}
Point pop(Queue* queue) {
	Point re;
	node* now;
	now = queue->front;
	re = now->point;
	queue->front = now->next;
	free(now);
	queue->count--;
	return re;
}
int empty(Queue* queue) {
	if (queue->count == 0) return 1;
	else return 0;
}
void bfs() {
	Queue queue;
	initQueue(&queue);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < n; k++) {
				if (arr[i][j][k] == 1) {
					push(&queue, i, j, k);
				}
			}
		}
	}
	int dx[] = { -1, 0, 1, 0, 0, 0 };
	int dy[] = { 0, -1, 0, 1, 0, 0 };
	int dz[] = { 0, 0, 0, 0, -1, 1 };
	while (!empty(&queue)) {
		Point p = pop(&queue);
		max = math_max(max, arr[p.z][p.x][p.y]);
		for (int i = 0; i < 6; i++) {
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];
			int nz = p.z + dz[i];
			if (0 <= nx && nx < m && 0 <= ny && ny < n && 0 <= nz && nz < h && arr[nz][nx][ny] == 0) {
				arr[nz][nx][ny] = arr[p.z][p.x][p.y] + 1;
				push(&queue, nz, nx, ny);
			}
		}
	}
}
main() {
	scanf("%d %d %d", &n, &m, &h);
	arr = (int***)malloc(sizeof(int**) * h);
	for (int k = 0; k < h; k++) {
		arr[k] = (int**)malloc(sizeof(int*) * m);
		for (int i = 0; i < m; i++) {
			arr[k][i] = (int*)malloc(sizeof(int) * n);
			for (int j = 0; j < n; j++) {
				scanf("%d", &arr[k][i][j]);
			}
		}
	}
	bfs();
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[k][i][j] == 0) {
					printf("-1");
					exit(0);
				}
			}
		}
	}
	printf("%d", max - 1);
}

자바를 이용한 풀이와 동일합니다. list는 따로 구현하지 않고 bfs 함수 내부에서 3중 for문을 활용하여 최초에 익은 상태의 토마토의 위치를 큐에 삽입했습니다.

---

결론

지난번에 풀었던 다른 토마토 문제를 2차원 그래프가 아닌 3차원 그래프로 표현한 문제였습니다. 처음에 3차원 그래프 문제를 봤을 때 약간 당황했지만 직접 3차원 그림을 종이에 그려보며 차근차근 접근해보니 쉽게 문제를 해결할 수 있었습니다.