백준 알고리즘 7576 토마토 문제풀이 해설과 소스

토마토를 영국에서는 "신이 주신 열매"라고 부릅니다.

그만큼 피로회복에도 좋고, 특히 토마토의 라이코펜 성분이 알코올 분해시 생성하는 독성물질을 배출한다고 하네요.

영국에서는 해장으로도 토마토를 섭취한다고하니, 가볍게 보였던 토마토가 웬지 오늘 따라 달라보이는군요.

크레이는 술을 먹지 않지만, 술 드시는 분은 다음날 해장국 대신 해장토마토를 권해드리는 바입니다. 그렇다고 술을 과음하시라는 이야기는 절대 아닙니다 :)

​

오늘 도전해본 백준 알고리즘 문제는 "토마토 익는 날짜" 계산하기 문제입니다.

​

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

7576번: 토마토

창고 안에 토마토가 보란듯이 격자 모양으로 상당한 양이 나열되어 있습니다.

토마토가 비어있는 칸도 있고, 토마토가 아직 익지 않은 칸도, 토마토가 익은 칸도 있습니다.

하루가 지나면 익은 토마토는 상하좌우의 토마토들을 마치 전염시키듯 익힙니다.

하루가 또 지나면 전날 익혀진 토마토들은 다시 상하좌우 토마토를 익힙니다.

( 단, 대각선으로는 익히지 않습니다 )

​

이 규칙을 적용하여 모든 토마토가 익는 날짜를 계산하는 것인데요.

예외사항이 있습니다.

토마토가 익혀지지 않는 경우가 존재하는데 이 경우 날짜를 -1일로 출력하는 것입니다.

​

과거에 유사 문제를 풀어본바가 있어 똑같은 방법으로 시도해보았는데..

시간 초과가 났습니다.

모든 행과 열을 조사하면서 하루에 한 단계씩 익히는 방법이었지요.

​

최대 1,000 X 1,000 칸의 공간이니 그런 방법으로는 제한시간 2초 내에는 처리가 안되었습니다.

​

이 경우 BFS 탐색 방식이 필요한데요.

BFS 탐색은 특정 지점에서 시작하여 접근 가능한 모든 지점을 후보로 등록하고,

다시 접근하여 이후로 접근 가능한 지점을 2차 후보로 등록, 이런 방식으로 무한 반복하다가 더 이상 접근할 곳이 없으면 끝내는 방법입니다.

그러면 필요한 부분만 접근하기 때문에 매우 속도가 빠릅니다.

​

이 과정에서 이미 접근한 지점은 방문표시를 해두는 부분이 필요한데요.

이 문제의 경우 토마토를 익은 표시를 해두면 되기 때문에

그 부분이 방문표시를 대체한다고 볼 수 있습니다.

​

한 예를 들어보겠습니다.

아래와 같이 토마토가 있는데요. 1은 익은 토마토, 0은 아직 익지 않은 토마토입니다.

익은 토마토가 있는 지점을 좌표로 표시하면 ( 0, 0 ), (5, 3 ) 입니다.

여기서 2개의 지점으로부터 상하좌우에 0으로 된 익지 않은 토마토를 익힙니다.

이 때 새로익은 토마토를 지도에는 0을 1로 표시를 바꾸고 토마토 목록에 추가합니다.

그러면 새로 익은 토마토 목록은 아래와 같겠지요?

( 0, 0 ), (5, 3 ), (0, 1), (5,2)

2개가 익었으니 소요일수를 하루 셉니다.

그리고 전날 있었던 2개는 더 이상 검사할 필요가 없으니 목록에서 뺍니다.

그러면 아래 2개가 남겠지요.

(0, 1), (5,2)

이어서 또 토마토를 익힙니다.

(0, 1), (5,2), (0,2), (5,1)

토마토가 익었으니 목록에서 앞의 2개를 뺍니다.

다시 2개가 남았습니다.

(0. 2), (5. 1)

​

그 다음으로 토마토가 익을 때는 갯수가 더 많습니다.

이제 3일이 되었군요.

(0. 2), (5. 1), (0, 3), (1, 2), (5, 0), (4, 1)

이런 식으로 토마토를 계속 오염(?)시키는 것입니다

​

전날 2개 빼기

(0, 3), (1, 2), (5, 0), (4, 1)

​

4일차 토마토 익히기

(0, 3), (1, 2), (5, 0), (4, 1), (1, 3), (2, 2), (4, 0), (3, 1)

전일 4개 빼기

(2,1), (3,2), (2, 3), (3,0)

​

6일차 토마토 익히기

(2,1), (3,2), (2, 3), (3,0), (2,0), (3, 3)

전일 토마토 4개 삭제

(2,0), (3, 3)

​

7일차를 토마토를 익히려고 보니, 더 익힐 토마토가 없습니다.

그러면 이 때는 소요일수를 세지 않습니다.

​

총 6일이 소요되었군요 :)

​

끝난걸까요?

아니오, 아직 하나가 더 남았습니다.

다른 경우를 예를 들면 아래와 같이 빨간 색 표시가 된 경우 모든 토마토를 익힐 수가 없습니다.

아무리 날짜가 흘러도 익은 토마토가 상하좌우 규칙으로 접근을 못하기 때문이지요.

이 경우 그냥 모든 행과 열을 찾아서,

아직 안 익은 토마토가 있는지 판단, 있다면 -1을 출력하고 끝내버리면 됩니다.

​

해설이 좀 장황했는데요. 어디까지나 이해를 위한 해설이고,

이제서야 소스 공개합니다 :)

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

// 토마토 창고
int map[1000][1000];

// 익는 현황
struct point2d {
	int x, y;
};
vector<point2d> ripe;

void Result()
{
	int m, n;	//  가로, 세로
	scanf("%d %d", &m, &n);
	
	// 토마토 창고 정보 읽기
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			scanf("%d", &map[i][j]);

	// 익어 있는 처음 열매 bfs 탐색 목록에 추가
	// 간선정보는 map 이 대체하므로 필요없다
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			if(map[i][j]==1){
				point2d tmp={j,i};
				ripe.push_back(tmp);
			}

	// 익는데 걸린 시간
	int days=0;
	bool changed=false;

	// 시뮬레이션 시작
	do
	{
		// 바뀌었나 여부
		changed=false;

		// 하루치의 갯수만 반복하기 위해 갯수 미리 보관
		long ripeCount = ripe.size();

		// 그날에 익어져 있던 토마토만 처리
		for(long i=0;i<ripeCount;++i)
		{
			int x = ripe[i].x;
			int y = ripe[i].y;
			// 맵을 벗어나지 않으면서 익지 않은 모든 토마토에 대해
			if(y>0   && map[y-1][x]==0){ 
				// 익힌 다음에
				map[y-1][x]=1;
				// 다음 날의 토마토 탐색 bfs 추가 저장
				point2d tmp={x,y-1}; 
				ripe.push_back(tmp);
				// 바뀌었다고 표시해준다
				changed=true; 
			}
			// 이하는 방향만 다르지 똑같은 부분
			if(x>0   && map[y][x-1]==0){ 				
				map[y][x-1]=1; 
				point2d tmp={x-1,y}; 
				ripe.push_back(tmp); 
				changed=true; 
			}
			if(y<n-1 && map[y+1][x]==0){ 
				map[y+1][x]=1; 
				point2d tmp={x,y+1}; 
				ripe.push_back(tmp); 
				changed=true; 
			}
			if(x<m-1 && map[y][x+1]==0){ 
				map[y][x+1]=1; 
				point2d tmp={x+1,y}; 
				ripe.push_back(tmp);
				changed=true; 
			}
		}

		// 그날 처리한 하루치는 더 이상 처리할 필요가 없으므로 날린다.
		// 한꺼번에 날려야 백준 문제를 통과할만큼 속도가 나온다.
		ripe.erase(ripe.begin(), ripe.begin() + ripeCount);

		// 바뀐게 없었으면 끝
		if(changed==false)break;

		// 바뀐게 있었으면 소요 일수 카운트
		days++;
	}while(true);

	// 모두 익었나 여부 판단
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j)
			if(map[i][j]==0){
				// 익지 않은 곳이 있으면
				// -1 출력하고 끝
				printf("-1");
				return;
			}

	// 익은 날짜 출력
	printf("%d", days);
}

int main()
{
	Result();
	getchar(); getchar();
}