[백준 / C언어] 7576번: 토마토 (BFS로 구현)

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

7576번: 토마토

 

난이도: solved.ac 골드 5

 

 

알고리즘 종류

---

BFS (너비 우선 탐색)

 

 

문제 설명

---

하루가 지나면 익은 토마토를 기준으로 상하좌우로 인접한 토마토들이 익게 된다

 

익은 토마토는 1, 아직 익지 않은 토마토는 0, 빈 칸은 -1로 표시된다

 

아래는 예제 입력 1의 토마토가 어떻게 익게 되는지 그림으로 나타낸 것이다

 

익은 토마토가 있는 칸은 파란색으로 칠해주었다

위의 예제 입력 1은 초기의 토마토가 단 하나이지만, 여러 개로 입력을 줄 수도 있다

 

아래는 초기의 토마토가 두 개인 예제 입력 3을 그림으로 나타낸 것이다

 

참고하면 이해하는 데에 도움이 될 것이다

 

 

접근 방법

---

토마토를 방문할 때마다 해당 위치를 큐에 넣어주는데, 방문한 토마토의 개수가 토마토의 총 개수와 다르면 '-1'을 출력하고,

 

같다면 마지막으로 넣었던 토마토가 며칠 차에 들어갔는지를 출력하도록 해주었다

 

이때 토마토가 며칠 차에 들어간건지는, 큐에 넣을 때 며칠 차에 익었는지 함께 저장하도록 하여 알 수 있다

 

구현

---

BFS를 위해 우선 큐(Queue)를 구조체 배열 형식으로 만들어주었다

 

이때 원소로는 행과 열의 위치를 나타낼 x, y, 그리고 해당 토마토가 며칠 차에 익는지를 나타내는 order가 있다

 

그리고 이 배열의 사이즈는 index를 1부터 시작할 거라 상자의 사이즈 + 1로 두었다

 

상하좌우로 이동하며 해당 위치의 토마토를 큐에 넣을 때는 그 위치의 값을 1로 만들어 나중에 중복해서 큐에 넣는 일이 없도로 해주었다

 

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

typedef struct _Queue {
	int x;	// 열
	int y;	// 행
	int order;	// 날짜 (몇 번째로 익는 차례인지)
} Queue;

int dy[4] = { 0,1,0,-1 };	// 행
int dx[4] = { 1,0,-1,0 };	// 열

int N, M;
int front, rear;
void BFS(int** box, Queue* q, int y, int x);

int main() {
	int i, j;
	scanf("%d %d", &M, &N);
	int** box = (int**)calloc(N, sizeof(int*));
	for (i = 0; i < N; i++)
		box[i] = (int*)calloc(M, sizeof(int));

	int total = N * M;
	Queue* q = (Queue*)calloc(N * M + 1, sizeof(Queue));
	front = 0, rear = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == -1)
				total--;
			else if (box[i][j]) {
				rear++;
				q[rear].y = i;
				q[rear].x = j;
				q[rear].order = 0;
			}
		}
	}
	
	BFS(box, q, q[0].y, q[0].x);

	if (total != rear)
		printf("-1");
	else
		printf("%d", q[rear].order);

	for (i = 0; i < N; i++)
		free(box[i]);
	free(box);
	return 0;
}

void BFS(int** box, Queue* q, int y, int x) {
	while (front < rear) {
		front++;
		for (int i = 0; i < 4; i++) {
			int ny = q[front].y + dy[i];
			int nx = q[front].x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M)
				continue;
			else {
				if (!box[ny][nx]) {
					rear++;
					q[rear].y = ny;
					q[rear].x = nx;
					q[rear].order = q[front].order + 1;
					box[ny][nx] = 1;
				}
			}
		}
	}
}