백준 7576번 토마토

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

 

아이디어:

1. 시작지점이 여러 곳인 BFS

큐에 한번에 넣어놨다가 for문으로 큐에 있는걸 전부 pop()하면서 BFS 수행하고 ans++

2. 입력 n, m이 반대인 것에 주의

3. 큐에 시작지점을 넣으면서 ans에 1이 추가되는 것에 주의, 따라서 ans = -1로 설정

4. 이중 for문으로 시작지점으로 있는 1을 모두 큐에 push()

5. Q.size()를 변수 s에 별도로 저장하여 for(int i = 0; i < Q.size(); i++)이 아닌 for(int i = 0; i < s; i++) 로 for문 작성

그렇지 않다면 BFS를 수행하며 Q에 다시 push()한 만큼 size()가 변경돼 반복을 더 수행한다.

6. 익은 토마토는 board[nx][ny]에 별도 표시

7. BFS를 끝내고 이중 for문으로 board를 순회하면서 안익은 토마토 (board[i][j] == 0)를 점검

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int board[1001][1001];
int vis[1001][1001];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	for (int i = 0; i < 1001; i++) {
		fill(board[i], board[i] + 1001, -1);
	}

	int n, m, s, ans = -1;
	bool possible = true;
	queue<pair<int, int>> Q;
	cin >> m >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 1) {
				vis[i][j] = 1;
				Q.push({ i, j });
			}
		}
	}

	while (!Q.empty()) {
		s = Q.size();

		for (int i = 0; i < s; i++) {
			pair<int, int> cur = Q.front();
			Q.pop();
			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
				if (vis[nx][ny] == 1 || board[nx][ny] != 0) continue;
				board[nx][ny] = 1;
				vis[nx][ny] = 1;
				Q.push({ nx, ny });
			}
		}

		ans++;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board[i][j] == 0) {
				possible = false;
			}
		}
	}

	if (possible) cout << ans;
	else cout << -1;

	return 0;

}

 

다른 방법으로

익은 토마토마다 거리를 달아주고 그 최대값을 출력하는 해가 있다.

이 방법은 큐에 한번에 push()하고 한번에 pop()할 필요 없이 통상 BFS 처럼 수행하고 거리만 표기하는 방법이다.

즉, 거리 = 토마토 익는 날짜

소요 시간은 같고 메모리도 큰 차이가 안난다.

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int board[1002][1002];
int dist[1002][1002];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> m >> n;
  queue<pair<int,int> > Q;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 1)
        Q.push({i,j});
      if(board[i][j] == 0)
        dist[i][j] = -1;
    }
  }
  
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] >= 0) continue;
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  
  int ans = 0;
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(dist[i][j] == -1){
        cout << -1;
        return 0;
      }
      ans = max(ans, dist[i][j]);
    }
  }
  cout << ans;
}