백준 7576번 C++

백준 7576번 토마토

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

7576번: 토마토

정답 코드

#include<iostream>
#include<queue>
using namespace std;
int arr[1001][1001];
int dis[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> m >> n;
	queue<pair<int, int>>q;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < m; y++) {
			cin >> arr[x][y];
			if (arr[x][y] == 1)
				q.push({ x,y });
			if (arr[x][y] == 0)
				dis[x][y] = -1;
		}
	}
	while (!q.empty()) {
		pair<int, int>cur = q.front();
		q.pop();
		for (int x = 0; x < 4; x++) {
			int mx = cur.first + dx[x];
			int my = cur.second + dy[x];
			if (mx < 0 || my < 0 || mx >= n || my >= m)
				continue;
			if (dis[mx][my] >= 0)
				continue;
			dis[mx][my] = dis[cur.first][cur.second]+1;
			q.push({ mx,my });
		}

	}
	int ans = 0;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < m; y++) {
			if (dis[x][y] == -1) {
				cout << -1;
				return 0;
			}
			ans = max(ans, dis[x][y]);
		}

	}
	cout << ans;
}

문제 풀이

백준 7569번 토마토 문제의 2차원 버전입니다.
bfs를 이용, 2차원 배열을 만들었고 움직일 수 있는 것들도 좌표를2개를 사용했습니다.
먼저 time배열을 -1로 초기화한 후 arr배열에 입력을 받고 입력값이 1이면 그때의 좌표값을 큐에넣고 time배열값을 0으로 바꾸었습니다. 나중에 for문을 돌려서 1을 찾는 반복성을 없애기 위함입니다.
그 후 bfs를 돌려주고 배열의 범위를 벗어나거나 time값이 0보다 큰 이미 방문한 곳은 continue시켰습니다.
arr[mx][my]값이 0일 경우에는 토마토가 익을 수 있는 곳이므로 큐에 좌표값을 삽입, time배열값 변경, arr값도 1로 변경(토마토가 익음)하였습니다.
마지막으로 time배열을 돌리면서 최솟갑을 찾아주고
arr배열을 돌려서 만약 0이 있는 경우(토마토가 다 안익은 것이므로 실패)를 체크해줍니다.