토마토(7576)
#include <stdio.h>
#include <stdlib.h>
typedef struct t_node
{
int x, y, day;
struct t_node *next;
} node;
node *front, *rear;
int **flag, **box;
void init_queue(void)
{
front = (node *)malloc(sizeof(node));
rear = (node*)malloc(sizeof(node));
front -> next = rear;
rear -> next = rear;
}
void push(int x, int y, int d)
{
node *new;
new = (node *)malloc(sizeof(node));
new -> x = x;
new -> y = y;
new -> day = d;
if (front -> next == rear)
{
front -> next = new;
new -> next = rear;
rear -> next = new;
return ;
}
rear -> next -> next = new;
new -> next = rear;
rear -> next = new;
}
void pop(void)
{
node *curr;
curr = front -> next;
front -> next = curr -> next;
free(curr);
}
int BFS(int N, int M)
{
int ret, tmpx, tmpy;
while (front -> next != rear)
{
tmpx = front -> next -> x;
tmpy = front -> next -> y;
ret = front -> next -> day;
pop();
if (tmpx + 1 < M && flag[tmpy][tmpx + 1] == 0)
{
push(tmpx + 1, tmpy, ret + 1);
flag[tmpy][tmpx + 1] = 1;
}
if (tmpx - 1 >= 0 && flag[tmpy][tmpx - 1] == 0)
{
push(tmpx - 1, tmpy, ret + 1);
flag[tmpy][tmpx - 1] = 1;
}
if (tmpy + 1 < N && flag[tmpy + 1][tmpx] == 0)
{
push(tmpx, tmpy + 1, ret + 1);
flag[tmpy + 1][tmpx] = 1;
}
if (tmpy - 1 >= 0 && flag[tmpy - 1][tmpx] == 0)
{
push(tmpx, tmpy - 1, ret + 1);
flag[tmpy - 1][tmpx] = 1;
}
}
return (ret);
}
int main(void)
{
int N, M, day, tmpd;
scanf("%d%d", &M, &N);
flag = (int **)calloc(N, sizeof(int *));
box = (int **)calloc(N, sizeof(int *));
for (int i = 0; i < N; i++)
{
flag[i] = (int *)calloc(M, sizeof(int));
box[i] = (int *)calloc(M, sizeof(int));
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
scanf("%d", &box[i][j]);
if (box[i][j] == -1)
flag[i][j] = -1;
}
init_queue();
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (flag[i][j] == 0 && box[i][j] == 1)
{
push(j, i, 0);
flag[i][j] = 1;
}
day = BFS(N, M);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (!flag[i][j])
day = -1;
printf("%d\n", day);
for (int i = 0; i < N; i++)
{
free(flag[i]);
free(box[i]);
}
free(flag);
free(box);
return (0);
}
전에 쓴 미로 찾기보다는 정리된 것 같은데, 더럽당
#include <stdio.h>
#include <stdlib.h>
typedef struct t_node
{
int x, y, day;
struct t_node *next;
} node;
node *front, *rear;
int **flag, **box;
헤더는 표준 입출력 라이브러리, C 표준 유틸 라이브러리를 사용했고
큐는 x값, y값, 며칠이 걸리는지를 카운트한다.
scanf("%d%d", &M, &N);
flag = (int **)calloc(N, sizeof(int *));
box = (int **)calloc(N, sizeof(int *));
for (int i = 0; i < N; i++)
{
flag[i] = (int *)calloc(M, sizeof(int));
box[i] = (int *)calloc(M, sizeof(int));
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
{
scanf("%d", &box[i][j]);
if (box[i][j] == -1)
flag[i][j] = -1;
}
init_queue();
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (flag[i][j] == 0 && box[i][j] == 1)
{
push(j, i, 0);
flag[i][j] = 1;
}
day = BFS(N, M);
메인 함수는 M(가로 길이), N(세로 길이)를 받아 전부 전역 변수인 flag와 box 변수를 초기화 한 후, 반복문을 이용해 box의 값을 채우고, -1이 입력되었을 경우에 flag의 해당 값만 -1로 만들어준다.
큐를 만들고 큐에 들어갈 수 있는 모든 수 (box에 1이 표현된 위치)를 미리 넣어준 후 BFS를 실행하여 day에 반환 값(토마토가 모두 익는 데에 필요한 일수)을 저장한다.
int BFS(int N, int M)
{
int ret, tmpx, tmpy;
while (front -> next != rear)
{
tmpx = front -> next -> x;
tmpy = front -> next -> y;
ret = front -> next -> day;
pop();
if (tmpx + 1 < M && flag[tmpy][tmpx + 1] == 0)
{
push(tmpx + 1, tmpy, ret + 1);
flag[tmpy][tmpx + 1] = 1;
}
if (tmpx - 1 >= 0 && flag[tmpy][tmpx - 1] == 0)
{
push(tmpx - 1, tmpy, ret + 1);
flag[tmpy][tmpx - 1] = 1;
}
if (tmpy + 1 < N && flag[tmpy + 1][tmpx] == 0)
{
push(tmpx, tmpy + 1, ret + 1);
flag[tmpy + 1][tmpx] = 1;
}
if (tmpy - 1 >= 0 && flag[tmpy - 1][tmpx] == 0)
{
push(tmpx, tmpy - 1, ret + 1);
flag[tmpy - 1][tmpx] = 1;
}
}
return (ret);
}
큐에 필요한 값들을 모두 넣어놓았으니, 큐의 값을 빼서 인접한 행렬을 큐에 넣어주는 작업을 반복한다.
해당 작업을 한 후엔 flag 배열에서 익을 수 있는 토마토는 전부 익어 1이 되어있는 상태이고, 토마토가 없는 부분은 -1, 근처에 익은 토마토가 인접하지 않은 부분은 BFS가 끝난 후 아직 0이다.
day = BFS(N, M);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (!flag[i][j])
day = -1;
printf("%d\n", day);
for (int i = 0; i < N; i++)
{
free(flag[i]);
free(box[i]);
}
free(flag);
free(box);
return (0);
}
반복문으로 배열을 전부 순회하여 0이 있다면 위에서 저장해 둔 day의 값을 걸리는 일 수가 아닌 -1로 변경한 후
day를 출력
한 후 할당한 배열을 전부 해제한 후 프로그램을 종료한다.