[c 알고리즘] 백준 7576 토마토 문제 해설

(문제의 서술은 생략하겠습니다.)

 

이 문제에서 요구하는 토마토가 모두 익으려면 얼마나 걸리는지 그 최소 일수를 알고 싶어한다.

 

확산을 하며 조건을 만족하기 위한 최소값을 구하라?? 이게 바로 BSF로 해결하면 되는 문제입니다.

 

근데, 이번에는 시작점과 끝점을 정해준 것이 아니며, 심지어 시작 위치는 동시에 여러 곳 일 수 있습니다.

 

그렇다면 이 문제를 어떻게 해결하면 좋을까요? BSF와 짝궁으로 같이 다니는 큐를 활용하면 됩니다.

반응형

큐는 FIFO(First In First Out)구조이기 때문에 원하는 값을 넣어준 순서대로 다시 빼와서 활용하기에 적합합니다.

 

따라서 서로 다른 시작위치를 큐에 push 해 두었다가 pop으로 꺼내서 다음 위치로 이동시키면 됩니다. 

 

이제 BSF를 활용한 방법을 같이 확인해보겠습니다. 

 

BSF는 다음과 같이 단계를 나누어 생각하면 많은 도움이 됩니다.

1. 초기화
2. 시작 위치 큐에 저장(방문 확인 필요)
3. 반복문(범위 확인 필요, 방문확인 필요)
4. 실패

그럼 코드로는 어떻게 구현 되는 지 알아보겠습니다.

 

#include <stdio.h>
#define MAXN (1000)
int M, N;//가로(열), 세로(행) 
int map[MAXN + 10][MAXN + 10];//토마토 정보
int wp; // write pointer
int rp; // read pointer




//****************************[큐 관련 한수 제작]******************************//


// 구조체는 아래와 같이 typedef를 이요하여 사용하면 편리합니다.
typedef struct _ {
	int m;
	int n;
	int day;
}QUE;

QUE que[MAXN * MAXN + 10]; 

void push(int n, int m, int day)
{
	// push 함수의 파라미터로 가로 위치, 세로 위치, 경과일수를 받습니다.
	que[wp].m = m;
	que[wp].n = n;
	que[wp++].day = day;
}

QUE pop(void)
{
	// pop 함수는 현재 rp가 가르키는 값을 QUE type(구조체)으로 리턴합니다.
	return que[rp++];
}

int empty(void)
{
	return wp == rp; // wp와 rp가 같다는 뜻은 큐가 비어있다는 뜻입니다.
}

//***********************************************************************//

//*******************************[BSF 함수 제작]*********************************//



int BSF(void)
{
	// 0. 위치 이동 배열
	int dn[] = { -1, 1, 0, 0 }; //상하좌우(행방향으로만 이동, 좌상단이 (0,0)입니다.)
	int dm[] = { 0, 0, -1, 1 }; // 상하좌우 (열방향으로만 이동, 좌상단이 (0,0)입니다.)

	// 1. 초기화
	wp = 0;
	rp = 0;
	int zero_cnt = 0; //안익은 토마토 개수 파악하기 위한 변수.

	QUE cur; // 현재 위치를 담는 변수.

	// 2. 시작 위치 push로 큐에 전달
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] == 1) // 1은 익은 토마토를 뜻하고, 시작지점이 된다.
			{
				push(i, j, 0); // 큐에 시작지점의 위치를 담아준다.
			}
			else if (map[i][j] == 0)
			{
				zero_cnt++; // 안익은 토마토 개수 증가 
			}
		}
		if (zero_cnt == 0) return 0; // 안익은 토마토가 없음
	}


	// 3. 반복문
	while (rp < wp)
	{
		cur = pop(); //현재 위치 저장.
		

		for (int i = 0; i < 4; i++) // 상하좌우만 확인할 것이니 4번만 반복
		{
			
			int newm = cur.m + dm[i]; // 새로운 열 위치 획득
			int newn = cur.n + dn[i]; // 새로운 행 위치 획득
			if ((newm < 0) || (newn < 0) || (newm >= M) || (newn >= N)) continue; // 범위 확인
			if (map[newn][newm] != 0) continue; // 익은 토마토면 다른 위치 탐색
			//if (--cnt == 0) return cur.day + 1; // 안익은 토마토 없으면(모두 익었으면) 일수 리턴
			push(newn, newm, cur.day + 1);
			map[newn][newm] = 1;// 방문 표시
			zero_cnt--;

		}

	}
	// 4. 실패 (반복문을 빠져나왔다는 것은 반복문 안에 우리가 원하는 조건을 만족하지 못했다는 것임, 안익은 토마토가 남아있음)
	// 큐가 빈 상태를 뜻함. 모두 익은 상태면 최소일자를 리턴 아니면 -1리턴.
	if (zero_cnt == 0) return cur.day;
	return -1;

}


void InputData(void) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

int main(void) {
	int ans = -1;
	InputData();//입력

	ans = BSF();

	printf("%d\n", ans);//출력
	return 0;
}

 

코드가 점점 길어지죠..?? 한번에 다 이해못하시더라도 구간별로 나눠서 반복해서 보시면 이해가 되실꺼라고 생각됩니다.

 

중요한건 꺾이지 않는 마음이죠?!

 

그럼 다음 포스팅에서 또 찾아 뵙겠습니다.