[백준 7576, 7569] 토마토

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

이전에 짰던 코드는 다음과 같다. 

#include <cstdio>
#include <vector>
#include <queue>
int M, N;
int box[1000 + 10][1000 + 10];
int visited[1000 + 10][1000 + 10];
int cnt;
int no_tomato;
int min_day;

struct _st
{
	int x;
	int y;
	int d;
};


std::queue<_st> Q;


void input(void)
{
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &box[i][j]);
			if (box[i][j] == 1) Q.push({i, j, 1});
			if (box[i][j] == -1) no_tomato++;			// 맵에서 -1의 개수
		}
	}
}



void init(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = 0x7fffffff;
		}
	}
}



void BFS(void)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };


	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		visited[data.x][data.y] = data.d;		// 토마토 위치 표시

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
			int nd = data.d + 1;
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1 || box[nx][ny] == -1) continue;
			if (visited[nx][ny] <= nd) continue;
			visited[nx][ny] = nd;
			Q.push({ nx, ny , nd });
		}
	}
}




int get_min_days(void)
{
	int min_day = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (visited[i][j] != 0x7fffffff) {
				cnt++;
				min_day = (min_day < visited[i][j]) ? visited[i][j] : min_day;
			}
		}
	}
	return min_day - 1;
}



int get_tomato(void)
{		
	if (!no_tomato && Q.size() == N * M) return 0;	// 저장될 때 부터 모든 토마토가 익어있는 상태 => 0 출력
	if (no_tomato + Q.size() == N * M) return 0;	// 익지않은 토마토가 없는 상태 => 0 출력

	// 토마토가 있는 좌표들을 기준으로 탐색 
	init(); // std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0x7fffffff)	// memset(visited, 1Byte, sizeof(visited))
	BFS();
	int days = get_min_days();
	if (cnt + no_tomato == N * M) return days;
	return -1;
}



int main()
{
	input();
	int ans = get_tomato();
	printf("%d\n", ans);
	return 0;
}

일단.. 내 코드는 길고 효율이 좋지 않다(메모리 : 21400kb, 시간 : 124ms). 

사실 줄이려면 더 줄일 수는 있을 것 같긴 한데 일단 AC 받았으므로 오늘은 여기까지 할랩.. 구려도 일단 돌아갔으면 된거잖아요 ? 

 

// input( );

오늘의 컨셉은 탑다운 ㅋ 입력함수부터 간다. 

처음 코드를 짤 때는 토마토가 있는 위치를 벡터에 입력받아서 그걸 또 하나씩 탐색해줬다. 근데 이렇게 하면 44%에서 타임아웃 난다. 

엄청 킹받게 하지만 내가 참 애정하는 애가 "BFS를 한 번만 돌리라"고 힌트를 줘서, 토마토가 있는 위치(즉 맵에서 1)를 담을 컨테이너로 큐를 선택했다. 큐의 원소들을 하나씩 꺼내며 인접한 곳 부터 탐색을 하기 위함이다. 

그리고 "저장될 때 부터 모든 토마토가 익어있는 상태(맵 전체가 0)"이거나, "익지 않은 토마토가 없는 상태(맵에 0이 없음)"라면 BFS 함수를 부르기도 전에 바로 리턴시켜주기 위해 no_tomato변수에 -1 위치의 개수를 쌓아주었다. 

 

 

// BFS( ) 함수

큐에서 원소(토마토가 있는 위치)를 하나씩 꺼내면서 탐색하도록 한다. 

방문 배열을 1이 아니라 nd = data.d + 1로 초기화한 이유는 "토마토가 익을 때 까지의 최소 날짜"를 구해야하기 때문이다. 서로 다른 위치의 토마토에 영향을 받아 익어갈 때, 더 적은 시간이 걸린 경우를 채택하도록 한 것이다. 

 

 

// get_min_days( ) 함수

여기서는 BFS 함수를 통해 갱신한 visited배열에서 0x7fffffff 를 제외하고 가장 큰 값을 선택해준다. 

그 이유는 최소 날짜를 구하라고 했지만, 어쨌든 그 날짜가 지나야만 모든 토마토들이 익을 수 있기 때문이다. 

리턴 시 min_day - 1을 해주는 이유는, 초기값을 1로 설정해줬기 때문이다. 원래 익은 토마토가 있던 자리는 굳이 하루가 지나지 않아도 되지만, 구현의 편의상 이렇게 설정해주었기 때문에 가장 마지막에 1을 빼준다. 

 

// get_tomato( ) 함수

익은 토마토의 개수와 원래 토마토가 없던 좌표의 수를 더해 맵 크기가 만들어지면 날짜를 리턴하고, 그게 아니라면 맵에 있는 모든 토마토를 익게 할 수 없는 경우이므로 -1을 리턴한다. 

 

 

++ 22.10.15 새로 짠 코드 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
int N, M;
int tomato[1000 + 2][1000 + 2];
int visited[1000 + 2][1000 + 2];
int zero;

struct _vt
{
	int x, y;
};

std::vector<_vt> T;

struct _qt
{
	int x, y;
	int time;
};

void input()
{
	scanf("%d %d", &M, &N);	// 열 행 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &tomato[i][j]);
			if (tomato[i][j] == 1) T.push_back({ i, j });
			else if (tomato[i][j] == 0) zero++;
		}
	}
}

int BFS()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	std::queue<_qt> Q;
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), -1);
	int total_time = 0;
	
	for (int i = 0; i < T.size(); i++) {
		int x = T[i].x;
		int y = T[i].y;
		Q.push({ x, y , 0});
		visited[x][y] = 0;
	}

	int cnt = 0;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (visited[nx][ny] >= 0) continue;
			if (tomato[nx][ny] == -1) continue;
			Q.push({ nx, ny , data.time + 1});
			visited[nx][ny] = data.time + 1;

			if (tomato[nx][ny] == 0) {
				cnt++;
				total_time = (visited[nx][ny] > total_time) ? visited[nx][ny] : total_time;
			}
		}
	}
	//debug();
	if (cnt != zero) return -1;
	return total_time;
}




int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

---

2차원 토마토를 풀었다면? => 3차원 토마토도 풀어보자 !

https://www.acmicpc.net/problem/7569

7569번: 토마토

#include <cstdio>
#include <queue>
#include <cstring>
int C, R, H;
int board[100 + 2][100 + 2][100 + 2];

struct _st
{
	int h;
	int x, y;
};

std::queue<_st> Q;
int visited[100 + 2][100 + 2][100 + 2];
int max_days;
int tomato;


void debug()
{
	for (int h = 0; h < H; h++) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				printf("%d", visited[h][i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}

}


void input()
{
	scanf("%d %d %d", &C, &R, &H);

	memset(visited, -1, sizeof(visited));
	for (int h = 0; h < H; h++) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				scanf("%d", &board[h][i][j]);
				if (board[h][i][j] == 1) {
					Q.push({ h, i, j });
					visited[h][i][j] = 0;
				}
				else if (board[h][i][j] == 0) tomato++;	// 익지않은 토마토 개수 세어놓음 
			}
		}
	}
}


int BFS()
{
	int dh[2] = { 1, -1 };
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };

	int get_dec = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		// 너비
		for (int p = 0; p < 4; p++) {
			int nx = data.x + dx[p];
			int ny = data.y + dy[p];
			
			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[data.h][nx][ny] == -1) continue;
			if (visited[data.h][nx][ny] >= 0) continue;
			if (board[data.h][nx][ny] == 0) {
				get_dec++;
				Q.push({ data.h, nx, ny });
				visited[data.h][nx][ny] = visited[data.h][data.x][data.y] + 1;
				if (max_days < visited[data.h][nx][ny]) max_days = visited[data.h][nx][ny];
			}
		}
		// 상하
		for (int p = 0; p < 2; p++) {
			int nh = data.h + dh[p];

			if (nh < 0 || nh >= H) continue;	//범위!!!! 높이 0 ~ H - 1 까지임... 멍청아..
			if (board[nh][data.x][data.y] == -1) continue;
			if (visited[nh][data.x][data.y] >= 0) continue;
			if (board[nh][data.x][data.y] == 0) {
				get_dec++;
				Q.push({ nh, data.x, data.y });
				visited[nh][data.x][data.y] = visited[data.h][data.x][data.y] + 1;
				if (max_days < visited[nh][data.x][data.y]) max_days = visited[nh][data.x][data.y];
			}
		}
	}
	//debug();
	return get_dec;
}


int main()
{
	input();
	int cnt = BFS();
	if (tomato == 0) printf("%d\n", 0);	// 안익은 토마토 없음 
	else if (cnt == tomato) printf("%d\n", max_days);
	else printf("%d\n", -1);
	return 0;
}