토마토

---

문제풀이

1. 모든 토마토가 있는 지점에서 상하좌우로 퍼져나가므로, BFS로 풀면 된다.
2. queue를 만들어, 반복문으로 토마토가 있는지점을 모두 넣어준다.
3. queue가 빌때까지 요소를 하나씩 front, pop해가면서 농장을 채워 넣는다.
4. 며칠이 지났는지 체크를 해야하므로, 날짜가 지나는지점을 알아야하는데, 여기에서는 firstNode라는 변수를 설정해서, 날짜가 바뀌고 첫번째 생성되는 토마토 위치를 firstNode에 담았다. 그리고 그 firstNode에 해당하는 토마토가 다른토마토를 생성하려 반복문에서 실행될때 초기화 및 지금 생성될 토마토를 저장했다.

말이 복잡한데 코드로 보면 이해가 쉬울것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>
using namespace std;
#define endl "\n"



#define MAX 1000+1
int m, n;
int board[MAX][MAX];
queue<pair<int, int>> q;
int dy[] = { 0,0,1,-1 };
int dx[] = { 1,-1,0,0 };
int cnt;

void bfs() {

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (board[i][j] == 1)
			{
				q.push({ i,j });
			}
		}
	}
	pair<int, int> firstNode = { 0,0 };
	while (!q.empty())
	{
		pair<int, int> v = q.front();

		if (v.first == firstNode.first && v.second==firstNode.second){
			cnt++;
			firstNode = { 0,0 };
		}

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = v.second + dx[i];
			int ny = v.first + dy[i];

			if (nx < 1 || nx > m || ny <1 || ny >n)
			{
				continue;
			}

			if (board[ny][nx] == 0)
			{
				board[ny][nx] = 1;
				q.push({ ny,nx });
				if (firstNode == make_pair(0, 0))
				{
					firstNode = { ny,nx };
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (board[i][j] == 0) {
				cnt = -1;
			}
		}
	}

	cout << cnt;

}

firstNode 변수를 이용하지 않은 깔끔한 코드

firstNode변수를 이용하지않고, board에 날짜를 기록해가면서 반복문을 이어가면 더 깔끔한 코드를 작성할 수 있다

void bfs() {
	while (!q.empty())
	{
		pair<int, int> v = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = v.second + dx[i];
			int ny = v.first + dy[i];

			if (nx < 1 || nx > m || ny <1 || ny >n)
			{
				continue;
			}

			if (board[ny][nx] == 0)
			{
				board[ny][nx] = board[v.first][v.second]+1; // 추가된 부분! 보드에 날짜를 기록
				q.push({ ny,nx });
			}
		}
	}
}

실력 향상

매일 자기전 연등시간에 2시간 시간내서 알고리즘 문제를 풀고있다.
2주 정도가 지났는데 확실히 실력이 늘은것이 보인다. 예전에 골드문제가 나오면 풀이방법도 안떠오르고, 머리에 있는걸 코드에 옮기기도 힘들었는데 향상된 부분이 눈에 보인다.
꾸준히해서 플래가자!

참고

https://jdselectron.tistory.com/55 코드단축 및 디버깅 팁