BaekJoon 7576 토마토

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

소스결과 7096KB 104ms

출처 Backjoon, 한국올림피아드 시,도 지역 본선 고등부 1번

언어 C++ 14

 

설명

시작지점이 여러군데인 BFS 문제이다.

일수를 구분 해야하기 때문에 오늘에 해당하는 Queue와 내일 확인해야할 Queue로 분리해서 문제를 풀었다.

 

익은 토마토를 기점으로 주변으로 1칸씩 확산하는 BFS이기에 문제 자체는 간단하다.

또한 box의 내용이 변경되어도 괜찮기에 새로 익은 토마토가 있다면 해당 위치의 값을 1로 바꿔주는게 좋다.

안바꿔서 많이 틀렸다

 

알고리즘

1. box의 초기 상태를 입력 받으면서 1인 위치를 todayQ에 추가

2. todayQ가 비어있는 상태인지 확인

3. todayQ에서 토마토위치를 기점으로 BFS를 진행, 새로 추가되는 지점은 tomorrowQ에 저장

4. tomorrowQ가 비어있지 않다면 빌때까지 원소를 꺼내 todayQ에 추가

5. 날짜를 표시하는 변수 + 1

6. 출력

 

사용예제

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	8
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	-1
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	6
2 2 1 -1 -1 1	0
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 1 1 0 0 1	1
4 1 1 0 0 0	3

 

소스코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

short box[1000][1000];
bool checkBox[1000][1000];

int posX[4] = { 1 , 0 , -1 , 0 };
int posY[4] = { 0, 1, 0, -1 };

struct Point {
	short x;
	short y;

	Point(short x, short y) : x(x), y(y) {}
};

int main()
{
	int row, col;
	int day = -1;
	queue<Point> todayQ;
	queue<Point> tomorrowQ;

	cin >> col >> row;

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
		{
			scanf("%hd", &box[i][j]);

			if (box[i][j] == 1)
				todayQ.push(Point(i, j));
		}

	if (todayQ.empty())
		day = 0;

	while (!todayQ.empty())
	{
		while (!todayQ.empty())
		{
			Point cur = todayQ.front();
			todayQ.pop();

			if (checkBox[cur.x][cur.y])
				continue;

			checkBox[cur.x][cur.y] = true;

			for (int i = 0; i < 4; i++)
			{
				int nextX = cur.x + posX[i];
				int nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < row && 0 <= nextY && nextY < col)
				{
					if (box[nextX][nextY] == 0 && !checkBox[nextX][nextY])
					{
						box[nextX][nextY] = 1;
						tomorrowQ.push(Point(nextX, nextY));
					}	
				}
			}
		}

		while (!tomorrowQ.empty())
		{
			todayQ.push(tomorrowQ.front());
			tomorrowQ.pop();
		}
		day++;
	}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			if (checkBox[i][j] == false && box[i][j] != -1)
			{
				cout << -1;
				return 0;
			}

	cout << day;

	return 0;
}