토마토
20 October 2019
문제 : https://www.acmicpc.net/problem/7576
이번은 BFS로 토마토를 익히는 문제를 풀어보도록 하겠습니다.
#include<stdio.h>
static int X, Y, count = 1;
static int** mat;
static int max = 0;
int head = 0;
int tail = 0;
const int arr_size = 1000001;
struct Node
{
int x, y;
Node* myAlloc(int x, int y) {
this->x = x;
this->y = y;
return this;
}
}a[arr_size];
void add(int x, int y) {
if (tail >= arr_size)
{
tail -= arr_size;
}
a[tail++].myAlloc(x, y);
}
Node* pull() {
if (head == tail)
{
return NULL;
}
if (head >= arr_size)
{
head -= arr_size;
}
return &a[head++];
}
void bfs();
bool isEnded();
int main(void) {
scanf("%d %d", &Y, &X);
mat = new int*[X];
for (int i = 0; i < X; i++)
{
mat[i] = new int[Y];
for (int k = 0; k < Y; k++)
{
int val;
scanf("%d", &val);
mat[i][k] = val;
if (mat[i][k] == 1)
{
add(i, k);
}
}
}
bfs();
if (!isEnded())
{
printf("-1");
}
else if (max == 0)
{
printf("%d", max);
}
else {
printf("%d", max - 1);
}
}
bool isEnded() {
for (int i = 0; i < X; i++)
{
for (int k = 0; k < Y; k++)
{
if (mat[i][k] == 0)
{
return false;
}
}
}
return true;
}
void resolve(int x, int y, int val) {
if (x < 0 || y < 0 || x >= X || y >= Y)
{
return;
}
if (mat[x][y] != 0)
{
return;
}
mat[x][y] = val;
if (val > max)
{
max = val;
}
add(x, y);
}
void bfs() {
Node* node = pull();
while (node != NULL)
{
resolve(node->x - 1, node->y, mat[node->x][node->y] + 1);
resolve(node->x + 1, node->y, mat[node->x][node->y] + 1);
resolve(node->x, node->y - 1, mat[node->x][node->y] + 1);
resolve(node->x, node->y + 1, mat[node->x][node->y] + 1);
node = pull();
}
}
이후, queue에 (0,0)을 넣고, queue에 있는 값 중에서 주변 값이 1이면, 해당 값을 현재 값보다 1을 더해줍니다.
그렇게 되면, 현재 가운데 값이 1인 경우, 상하좌우에 있는 1인 값을 가지고 있는 칸은 모두 2로 바뀌게 됩니다.
만약, 값을 바꾸려는 칸의 값이 1이 아닌 경우는 이미 다른 최단 경로를 통해 올 수 있으므로 값을 바꾸지 않고 넘어갑니다.
값을 바꾼 칸은 해당 칸을 기준으로 상하좌우 값을 또 바꿔야 하니, queue에 넣어줍니다.
해당 로직에 따라 queue에 값이 없을 때까지 반복해주도록 합니다.
매번 값을 업데이트할 때마다 최대값을 체크하여서 업데이트해주고, 가장 처음 값을 업데이트할 때 2가 되므로, max-1 만큼 return해주도록 합니다. 한번도 업데이트를 하지 않은 경우는 0 이므로, 그대로 return합니다. 또한, 전체 map을 검색하여 0이 하나라도 있는 경우는 업데이트에 실패한 경우이므로 -1을 return 해주도록 합니다.