BOJ 7576 : 토마토

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/7576

 

 

미로 탐색 문제에서 BFS를 이용하여 거리를 계산하였다.

 

같은 방법을 토마토 문제에서 적용할 수 있다.

토마토를 모두 넣고 미로 탐색과 같은 방식으로 BFS를 적용하면, 토마토가 상자를 꽉 채우게 된다.

토마토가 상자를 꽉 채우는 것은.

각 토마토가 상자에서 최소로 가능 경로를 모든 토마토에 대해 실행하면 된다.

 

다음과 같은 5 x 5 상자(MAP)에 토마토가 있다고 가정하자.

편의상(경계 조건을 신경쓰지 않기 위해) MAP의 주변은 -1로 만든다.

 

이제 모든 토마토를 queue에 담는다.

 

참고로 토마토 문제의 경우는 미로 탐색과는 달리 visit이 필요가 없다.

상자 자체를 visit으로 같이 사용할 수 있기 때문이다. 즉, 방문하지 않은 곳 = 토마토가 없는 곳인 0이다.

 

이제 토마토를 꺼내서, 주변 4방향을 토마토로 만든다. 벽(-1)과 이미 토마토가 있는 경우는 무시한다.

만든 토마토는 다시 큐에 넣는다. 큐에 넣을 때, pop해준 숫자에 + 1을 MAP에 표시한다. (날짜 세기)

 

다음 queue에 있는 토마토를 꺼내서, 주변을 토마토로 만들고, 만들어진 토마토는 다시 큐에 넣자.

 

여기까지 알 수 있는 점은, 토마토를 모두 큐에 넣고, BFS를 이용해 주변을 토마토로 만들었더니, 

모든 토마토가 동시에 주변을 토마토로 만든 것과 같은 효과가 된다는 것이다.

즉, 모든 시작점을 큐에 넣고 BFS를 실행하면 동시에 주변을 탐색하게 된다.

 

이렇게 계속 BFS를 실행하면 마지막으로 아래와 같은 MAP이 남게 된다.

MAP에 5가 남았다는 것은 최소 날짜가 4일이라는 뜻이된다. (1부터 세기 때문에)

---

이제 코드로 위의 내용을 구현해보자.

먼저 input에서는 주변을 벽으로 만들어야 한다.

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= M + 1; r++)
		for (int c = 0; c <= N + 1; c++)		
			MAP[r][c] = -1;

	for (int r = 1; r <= M; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

 

주변을 미리 벽으로 만들면, 경계 조건을 신경쓰지않고, 벽인지만 check하기 때문에 편하다.

 

4방향 탐색을 위해 dr, dc 배열을 만들고, BFS의 시작에 MAP[r][c] = 1(토마토)인 곳을 모두 큐에 담는다.

그리고 MAP[nr][nc] = 0인 곳, 즉 토마토가 없는 곳에만 토마토를 다시 만들고 큐에 담는다.

이때, MAP에 pop된 토마토의 MAP보다 +1씩 더해서 날짜를 센다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS()
{
	/* 모든 토마토를 먼저 담는다 */
	for (int r = 1; r <= M; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1)
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}

	while (wp > rp)
	{

		QUEUE out = queue[rp++];

		for (int k = 0; k < 4; k++)
		{
			int nr, nc;

			nr = out.r + dr[k];
			nc = out.c + dc[k];

			if (MAP[nr][nc] == 0) /* 주변이 빈 경우만 */
			{
				queue[wp].r = nr; /* 토마토를 담고 */
				queue[wp++].c = nc;
                
				MAP[nr][nc] = MAP[out.r][out.c] + 1; /* 날짜를 센다. */
			}
		}
	}
}

 

마지막으로 답을 찾는 과정에서, 벽 때문에 토마토가 모든 상자를 채우지 못하는 경우가 있는지 체크한다.

모든 상자를 채웠다면, 그 중 가장 큰 값에서 -1을 빼면 정답이 된다.

최초의 시작을 1로 했기 때문에, 토마토가 모두 익는 최소 날짜에서 -1을 빼야한다.

 

위의 구현은 최종 코드에서 findAns를 확인하면 된다.

#include <stdio.h>

#define MAX (1000 + 100)

int N, M;
int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}QUEUE;

QUEUE queue[MAX*MAX];
int wp, rp;

void input()
{
	scanf("%d %d", &N, &M);

	for (int r = 0; r <= M + 1; r++)
		for (int c = 0; c <= N + 1; c++)		
			MAP[r][c] = -1;

	for (int r = 1; r <= M; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &MAP[r][c]);
}

void output()
{
	for (int r = 0; r <= M + 1; r++)
	{
		for (int c = 0; c <= N + 1; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void BFS()
{
	for (int r = 1; r <= M; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1)
			{
				queue[wp].r = r;
				queue[wp++].c = c;
			}
		}
	}

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		for (int k = 0; k < 4; k++)
		{
			int nr, nc;

			nr = out.r + dr[k];
			nc = out.c + dc[k];

			if (MAP[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;
                
				MAP[nr][nc] = MAP[out.r][out.c] + 1;
			}
		}
	}
}

int findAns()
{
	int max = 0;
	for (int r = 1; r <= M; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 0) return -1;
			if (MAP[r][c] > max) max = MAP[r][c];
		}
	}

	return max - 1;
}

int main(void)
{
	input();

	BFS();

	printf("%d\n", findAns());

	return 0;
}

---

시작점을 모두 BFS에 넣기만 하면 2차원 MAP을 탐색할 수 있다는 것을 알 수 있게 되었다.

주로 바이러스 관련 문제에 이런 기법이 많이 쓰인다.

관련 문제는 삼성 A형 기출 문제인 연구소와 연구소 3을 풀어보자.