[C언어] 백준 7576 토마토

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1 

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 1 

8

예제 입력 2 

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력 2 

-1

예제 입력 3 

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력 3 

6

예제 입력 4 

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력 4 

14

예제 입력 5 

2 2
1 -1
-1 1

예제 출력 5 

0

 

bfs 살짝 심화 문제입니다.

너비 우선 탐색으로 맵을 전체 탐색할 때까지 총 몇번의 bfs를 수행했느냐를 묻는 문제인데요

 

먼저 이해하기 위해서 예제 1번을 봅시다.

// 0일차                    1일차                      2일차
0 0 0 0 0 0           0 0 0 0 0 0               0 0 0 0 0 0
0 0 0 0 0 0      ->   0 0 0 0 0 0         ->    0 0 0 0 0 3
0 0 0 0 0 0           0 0 0 0 0 2               0 0 0 0 3 2
0 0 0 0 0 1           0 0 0 0 2 1               0 0 0 3 2 1


// 3일차                    4일차                      5일차
0 0 0 0 0 4           0 0 0 0 5 4               0 0 0 6 5 4
0 0 0 0 4 3      ->   0 0 0 5 4 3         ->    0 0 6 5 4 3
0 0 0 4 3 2           0 0 5 4 3 2               0 6 5 4 3 2
0 0 4 3 2 1           0 5 4 3 2 1               6 5 4 3 2 1

// 6일차                     7일차                     8일차
0 0 7 6 5 4           0 8 7 6 5 4               9 8 7 6 5 4
0 7 6 5 4 3      ->   8 7 6 5 4 3         ->    8 7 6 5 4 3    // 8일차 때 모든 토마토가 익음
7 6 5 4 3 2           7 6 5 4 3 2               7 6 5 4 3 2
6 5 4 3 2 1           6 5 4 3 2 1               6 5 4 3 2 1

모든 토마토가 익을 때까지 총 8일이 걸리고 가장 높은 수는 9인것을 확인할 수 있습니다.

그럼 최종적으로 (가장 높은 수 - 1) == 모든 토마토가 익을 때까지의 최소 날짜

이런식으로 생각할 수 있겠네요 

 

그럼 문제를 풀기 위해 로직을 짜봅시다

 

우선 예외 처리 부분부터 생각해 보면

"저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고,

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다."

 

모든 토마토가 익어있을 때 0을 출력하는건 익지 않은 토마토는 0일 테니까 값을 변환 시켜주는건 0일 때만하면 되고

모든 토마토가 익지 못하는 상황이면 -1을 출력해야 한다.

-> 예제 2번과 같이 특정 위치에 bfs가 도달하지 못하는 경우(즉 방문할 수 없는 경우)

     이걸 bfs를 수행한 뒤 방문한 적이 없는 곳이 있다면 -1출력

 

이런식으로 예외처리를 하면 될것 같습니다.

 

그럼 예외 처리 부분은 됐고 이제 본문인 bfs를 만들 차례입니다.

bfs는 보통 큐 자료구조를 이용합니다.

 

C에서 큐 자료구조를 만드는 방법은 다양하겠지만 저는 양방향 연결 리스트를 구현해서 사용했습니다.

양방향을 쓴 이유는 편해서(?)입니다.

 

큐 && 양방향 연결 리스트 구현

#define MAX 2147483647
#define MIN -2147483648

typedef struct n
{
	int			nx;
	int			ny;
	struct n	*next;
	struct n	*prev;
} node;

node *head, *tail;

int	map[1001][1001], visited[1001][1001] = {}, x, y, total_day = MIN;

node *create_node(int nx, int ny)
{
	node *temp;

	temp = (node *)malloc(sizeof(node));
	temp->nx = nx;
	temp->ny = ny;
	temp->next = NULL;
	temp->prev = NULL;
	return (temp);
}

void create_queue(void)
{
	head = create_node(-1, -1);
	tail = create_node(-1, -1);
	head->next = tail;
	tail->prev = head;
}

void push(int nx, int ny)
{
	node *temp;
	node *last;

	temp = create_node(nx, ny);
	last = tail->prev;
	last->next = temp;
	temp->prev = last;
	temp->next = tail;
	tail->prev = temp;
}

node *pop(void)
{
	node *p;
	node *second;

	p = head->next;
	second = p->next;
	head->next = second;
	second->prev = head;
	return (p);
}

void queue_free(node *temp)
{
	if (temp->next != NULL)
		queue_free(temp->next);
	free(temp);
}

기본적인 push, pop과 노드 생성과 큐 생성을 하는 create_node, create_queue함수,

큐를 사용한뒤 할당 해제해주는 queue_free 함수입니다.

 

양방향 연결 리스트 이다 보니 push할 때 마지막 노드를 잡는게 많이 쉬웠습니다.

 

현재 위치 유망성 체크

int promising(node *n)
{
	if (n->nx < 0 || n->nx >= x || n->ny < 0 || n->ny >= y)
		return (0);
	if (visited[n->ny][n->nx] || map[n->ny][n->nx] == -1)
		return (0);
	visited[n->ny][n->nx]++;
	return (1);
}

현재 노드가 갖고 있는 nx, ny의 값이 맵을 벗어나지 않았는지, 이전에 방문한적이 있는지,

맵에서 -1(벽)의 값을 갖고 있는지를 체크해주는 promising 함수입니다.

 

유망할 때 상하좌우 노드 삽입

void insert(int nx, int ny)
{
	if (nx - 1 >= 0 && !visited[ny][nx - 1])
		push(nx - 1, ny);
	if (nx + 1 < x && !visited[ny][nx + 1])
		push(nx + 1, ny);
	if (ny - 1 >= 0 && !visited[ny - 1][nx])
		push(nx, ny - 1);
	if (ny + 1 < y && !visited[ny + 1][nx])
		push(nx, ny + 1);
}

현재 최상단 노드의 위치가 유망한 곳일 때 현재 위치로부터 상하좌우 노드를 삽입해 주어야 하는데요

이때 insert함수를 이용해 상하좌우 push해줍니다.

 

조건문을 걸어서 이전에 방문한적이 없으면서 맵을 벗어나지 않았을 때만 노드를 삽입해줍니다.

 

bfs 실행 횟수 체크

int	min(node *n)
{
	int min = MAX;

	if (n->nx - 1 >= 0 && min > map[n->ny][n->nx - 1] && map[n->ny][n->nx - 1] != 0 && map[n->ny][n->nx - 1] != -1)
		min = map[n->ny][n->nx - 1];
	if (n->nx + 1 < x && min > map[n->ny][n->nx + 1] && map[n->ny][n->nx + 1] != 0 && map[n->ny][n->nx + 1] != -1)
		min = map[n->ny][n->nx + 1];
	if (n->ny - 1 >= 0 && min > map[n->ny - 1][n->nx] && map[n->ny - 1][n->nx] != 0 && map[n->ny - 1][n->nx] != -1)
		min = map[n->ny - 1][n->nx];
	if (n->ny + 1 < y && min > map[n->ny + 1][n->nx] && map[n->ny + 1][n->nx] != 0 && map[n->ny + 1][n->nx] != -1)
		min = map[n->ny + 1][n->nx];
	return (min);
}

bfs를 한번씩 수행할 때마다 일수를 늘려야할 때 사용하는 min함수입니다.

상화좌우를 체크할 때 값이 0, -1, 맵을 벗어나지 않았는지를 체크하면서 가장 작은값을 도출해 내도록합니다.

 

bfs 시작 전 초기화

void init(void)
{
	node *n;

	scanf("%d %d", &x, &y);
	create_queue();
	for(int i = 0; i < y; i++)
	{
		for(int j = 0; j < x; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1)
				push(j, i);
			if (map[i][j] == -1)
				visited[i][j]++;
		}
	}
	if (head->next == tail)
		return ;
	n = pop();
	insert(n->nx, n->ny);
	visited[n->ny][n->nx]++;
	free(n);
}

bfs를 시작하기 전 모든 변수를 초기화 시켜주는 init함수입니다.

맵을 받았을 때 1이라면 push를 해줍니다.

 

만약 -1이라면 방문 처리를 해주는데요

0 0  0  0  1
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0  0  0  0

맵이 이런식인 경우 출력은 -1이 아니라 정삭적으로 나와야 하는데요

그럼 2, 2의 -1은 어떻게 처리를 해줄까 해서 아예 맵을 받을 때

-1인 경우 visited로 방문 처리를 했습니다.

 

main함수(bfs 실행)

int	main(void)
{
	node	*n;

	init();
	while (head->next != tail)
	{
		n = pop();
		if (!promising(n))
		{
			free(n);
			continue ;
		}
		if (map[n->ny][n->nx] == 0)
			map[n->ny][n->nx] = min(n) + 1;
		insert(n->nx, n->ny);
		free(n);
	}
        queue_free(head);
	for(int i = 0; i < y; i++)
	{
		for(int j = 0; j < x; j++)
		{
			if (!visited[i][j])
			{
				printf("-1\n");
				return (0);
			}
			if (total_day < map[i][j])
				total_day = map[i][j];
		}
	}
	printf("%d\n", total_day - 1);
	return (0);
}

처음에 모든 변수를 init함수를 호출해 초기화 시켜줍니다

 

이후 곧 바로 bfs를 실행합니다 끝나는 조건을 큐가 빌 때까지 반복을 하고

현재 위치가 유망하다면(promising함수 사용)

-> 현재 값을 min함수를 이용해 상하좌우 최소값 + 1 초기화, 현재 위치 상하좌우 큐 삽입

유망하지 않다면

-> 노드 free후 반복

 

이런식으로 bfs를 계속해서 실행을 해준뒤

큐를 queue_free로 해제해주고

 

이중 for문으로 전체 탐색을 해서 초기화된 맵에서 가장 큰 수를 찾습니다.

이때 만약 방문한적이 없는 경우 -1출력 후 종료를 해줍니다.

 

가장 큰 수를 찾고 가장 큰 수 -1을 출력해 주면 끝입니다.

 

 

반응형

전체 코드

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

#define MAX 2147483647
#define MIN -2147483648

typedef struct n
{
	int			nx;
	int			ny;
	struct n	*next;
	struct n	*prev;
} node;

node *head, *tail;

int	map[1001][1001], visited[1001][1001] = {}, x, y, total_day = MIN;

node *create_node(int nx, int ny)
{
	node *temp;

	temp = (node *)malloc(sizeof(node));
	temp->nx = nx;
	temp->ny = ny;
	temp->next = NULL;
	temp->prev = NULL;
	return (temp);
}

void create_queue(void)
{
	head = create_node(-1, -1);
	tail = create_node(-1, -1);
	head->next = tail;
	tail->prev = head;
}

void push(int nx, int ny)
{
	node *temp;
	node *last;

	temp = create_node(nx, ny);
	last = tail->prev;
	last->next = temp;
	temp->prev = last;
	temp->next = tail;
	tail->prev = temp;
}

node *pop(void)
{
	node *p;
	node *second;

	p = head->next;
	second = p->next;
	head->next = second;
	second->prev = head;
	return (p);
}

void queue_free(node *temp)
{
	if (temp->next != NULL)
		queue_free(temp->next);
	free(temp);
}

void insert(int nx, int ny)
{
	if (nx - 1 >= 0 && !visited[ny][nx - 1])
		push(nx - 1, ny);
	if (nx + 1 < x && !visited[ny][nx + 1])
		push(nx + 1, ny);
	if (ny - 1 >= 0 && !visited[ny - 1][nx])
		push(nx, ny - 1);
	if (ny + 1 < y && !visited[ny + 1][nx])
		push(nx, ny + 1);
}

void init(void)
{
	node *n;

	scanf("%d %d", &x, &y);
	create_queue();
	for(int i = 0; i < y; i++)
	{
		for(int j = 0; j < x; j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1)
				push(j, i);
			if (map[i][j] == -1)
				visited[i][j]++;
		}
	}
	if (head->next == tail)
		return ;
	n = pop();
	insert(n->nx, n->ny);
	visited[n->ny][n->nx]++;
	free(n);
}

int promising(node *n)
{
	if (n->nx < 0 || n->nx >= x || n->ny < 0 || n->ny >= y)
		return (0);
	if (visited[n->ny][n->nx] || map[n->ny][n->nx] == -1)
		return (0);
	visited[n->ny][n->nx]++;
	return (1);
}

int	min(node *n)
{
	int min = MAX;

	if (n->nx - 1 >= 0 && min > map[n->ny][n->nx - 1] && map[n->ny][n->nx - 1] != 0 && map[n->ny][n->nx - 1] != -1)
		min = map[n->ny][n->nx - 1];
	if (n->nx + 1 < x && min > map[n->ny][n->nx + 1] && map[n->ny][n->nx + 1] != 0 && map[n->ny][n->nx + 1] != -1)
		min = map[n->ny][n->nx + 1];
	if (n->ny - 1 >= 0 && min > map[n->ny - 1][n->nx] && map[n->ny - 1][n->nx] != 0 && map[n->ny - 1][n->nx] != -1)
		min = map[n->ny - 1][n->nx];
	if (n->ny + 1 < y && min > map[n->ny + 1][n->nx] && map[n->ny + 1][n->nx] != 0 && map[n->ny + 1][n->nx] != -1)
		min = map[n->ny + 1][n->nx];
	return (min);
}

int	main(void)
{
	node	*n;

	init();
	while (head->next != tail)
	{
		n = pop();
		if (!promising(n))
		{
			free(n);
			continue ;
		}
		if (map[n->ny][n->nx] == 0)
			map[n->ny][n->nx] = min(n) + 1;
		insert(n->nx, n->ny);
		free(n);
	}
    queue_free(head);
	for(int i = 0; i < y; i++)
	{
		for(int j = 0; j < x; j++)
		{
			if (!visited[i][j])
			{
				printf("-1\n");
				return (0);
			}
			if (total_day < map[i][j])
				total_day = map[i][j];
		}
	}
	printf("%d\n", total_day - 1);
	return (0);
}

 

 

맨 처음에 create_node, push 인자 nx, ny를 착각해서 ny, nx로 넣고 3시간 동안 왜 안되는지 찾고 있었네요 ㅠㅠ

여러분들은 이런 실수 없으시길