BaekJoon 7576번: 토마토

풀이법

BFS를 이용하여 문제를 해결하는 것이 가장 쉽게 문제를 해결할 수 있는 방법이다.

countNum 변수를 이용하여 최대 걸리는 시간을 계산한다면 쉽게 해결할 수 있다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int vx[4] = { 1,0,-1,0 };
int vy[4] = {0,-1,0,1};
int arr[1001][1001];
bool visited[1001][1001];
int n, m;
int countNum = 0;
void bfs()
{
	queue<pair<int, pair<int, int>>> q;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (arr[i][j] == 1) // 1인 것들 찾아서 넣는다.
			{
				visited[i][j] = true;
				q.push({ i,{j,0} });
			}
			if (arr[i][j] == -1)
			{
				visited[i][j] = true;
			}
		}
	}
	while (!q.empty())
	{
		int tempx = q.front().first;
		int tempy = q.front().second.first;
		int cnt = q.front().second.second;
		countNum = max(countNum, cnt);
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int tx = tempx + vx[i];
			int ty = tempy + vy[i];
			if (tx < 1 || tx>n || ty<1 || ty>m)
				continue;
			if (visited[tx][ty])
				continue;
			if (arr[tx][ty] == 0)
			{
				visited[tx][ty] = true;
				q.push({ tx,{ty,cnt + 1} });
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (arr[i][j] == 0 && visited[i][j] == false)
			{
				cout << -1;
				return;
			}
		}
	}
	cout << countNum;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> arr[i][j];
		}
	}
	bfs();
}

주의사항)

m과 n의 관계를 잘 살펴야 한다. main()안의 for문에서 i=행 j=열이다.

행과 열의 순서를 헷갈리게 되면 문제의 난이도가 어려워지므로 이 부분을 꼭 주의해서 볼 수 있도록 해야한다.

처음에 queue에 1인 것들의 count를 0으로 넣어서 FIFO 구조의 queue를 사용한다면 다 채워지는 시간을 구할 수 있을 것이다.

cin >> m >> n;
for (int i = 1; i <= n; i++)
{
	for (int j = 1; j <= m; j++)
	{
		cin >> arr[i][j];
	}
}

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest