백준 : 7576번, 토마토

문제 주소 : https://www.acmicpc.net/problem/7576

정답 비율 : 33.448% (2021.07.15. 20:18 기준)

7576번: 토마토

 

 

문제 요약 :

M x N 크기의 구역이 주어질 때 특정 칸들에는 1이 채워져 있고 특정 칸들에는 –1로 채워져 있고 나머지는 0으로 채워져 있습니다. 하루 지날 때마다 1로 채워져 있는 칸은 상, 하, 좌, 우 칸을 1로 채웁니다. 이때 –1로 채워져 있는 칸은 채울 수 없습니다.

이런 상황에서 0으로 채워진 모든 칸을 채우는 필요한 최소 일수를 구하면 됩니다.

 

문제 조건 :

입력 : 첫 줄에 M과 N이 차례대로 주어집니다. (M, N : 2 ~ 1000) 이어서 각 칸의 정보가 주어집니다.

출력 : 0으로 채워진 모든 칸을 1로 채우는 데 필요한 최소 일수를 출력

시간 : 1초

 

문제 풀이 :

BFS 문제입니다. 입력받을 때 1로 채워진 칸의 정보를 큐에 삽입 후에 하나씩 pop을 수행 후에 pop 한 데이터에 의해 영향받은 칸들을 다시 큐에 저장하는 형식으로 수행하면 됩니다. 이를 큐가 비었을 때까지 반복하면 됩니다.

 

 코드는 다음과 같습니다.

 

C99

// solve 7576
#include <stdio.h>
#include <stdlib.h>

#define QMAX 1000000

typedef struct _point {
	int x;
	int y;
}Point;

Point queue[QMAX];
int map[1000][1000];
int count = 0, front = -1, rear = -1;

int main(void) {

	int xMax, yMax;
	int dir_x[4] = { 1, -1, 0, 0 };
	int dir_y[4] = { 0, 0, 1, -1 };

	scanf("%d %d", &xMax, &yMax);

	for (int i = 0; i < yMax; i++) {
		for (int j = 0; j < xMax; j++) {
			scanf("%d", &map[i][j]);

			if (map[i][j] == 0)
				count++;
			else if (map[i][j] == 1)
			{
            	rear++;
                queue[rear].x = j;
                queue[rear].y = i;
			}
		}
	}

	if (count == 0) {
		printf("0");
	}
	else {
		while (rear != front) {
			int tx = queue[++front].x;
			int ty = queue[front].y;;

			for (int i = 0; i < 4; i++) {
				if (tx + dir_x[i] >= 0 && tx + dir_x[i] < xMax) {
					if (ty + dir_y[i] >= 0 && ty + dir_y[i] < yMax) {
						if (map[ty + dir_y[i]][tx + dir_x[i]] == 0) {
							map[ty + dir_y[i]][tx + dir_x[i]] = map[ty][tx] + 1;
                            
                            rear++;
                            queue[rear].x = tx + dir_x[i];
                            queue[rear].y = ty + dir_y[i];
							count--;
						}
					}
				}
			}
		}

		printf("%d", count == 0 ? map[queue[rear].y][queue[rear].x] - 1 : -1);
	}
	return 0;
}

-> M와 N의 최대 값에 따라서 큐의 최대 크기는 1,000,000입니다.

-> count는 0인 칸의 개수를 가지고 있는 변수입니다.

-> map에 직접 해당 칸이 1로 바뀌는데 걸리는 요일 수 + 1을 저장합니다. (시작 수가 1로 시작하기 때문입니다.)