BOJ 7576 - 토마토

토마토(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에 반환 값(토마토가 모두 익는 데에 필요한 일수)을 저장한다.

BFS 함수

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를 출력한 후 할당한 배열을 전부 해제한 후 프로그램을 종료한다.