[백준/C++]#7576 - 토마토

풀이

#include <cstdio>
#include <queue>
using namespace std;
 
int N, M;
int a[1001][1001];
int ck[1001][1001];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
 
int main() {
	queue<pair<int,int>> q;	// pair 받는 큐 선언
	scanf("%d %d", &M, &N);
	for (int i=0; i<N; i++) {
		for (int j=0; j<M; j++) {
			scanf("%d", &a[i][j]);	// 입력
			ck[i][j]=-1;	// ck 배열 값 초기화
			if (a[i][j] == 1) {		// 입력 값에 따라 어떤 값은 queue에 push
				q.push(make_pair(i, j));
				ck[i][j] = 0;
		}
	}
}

	while (!q.empty()) {
		int n = q.front().first;
		int m = q.front().second;
		q.pop();
		for (int k=0; k<4; k++) {
			int nx = n + dx[k];
			int my = m + dy[k];
			if (0<=nx && nx<N && 0<=my && my<M) {
				if (a[nx][my]==0 && ck[nx][my]==-1) {
					q.push(make_pair(nx, my));
					ck[nx][my] = ck[n][m]+1;	// 다음 ck 배열 값에 + 1
				}
			}
		}
	}
	int ans = 0;
	bool flag = false;
	for (int i=0; i<N; i++) {
		for (int j=0; j<M; j++) {
			if (ans <= ck[i][j]) {		// 가장 큰 값을 날짜 값으로 받음
				ans = ck[i][j];
			}
			if (a[i][j] == 0 && ck[i][j] == -1) {	// for문 탈출
				ans = -1;
				flag = true;
				break;
			}
		}
		if (flag == true) {		// 이중 for문 탈출
			break;
		}	
	}
	printf("%d", ans);
	return 0;
}

개념

이중 for문을 탈출하는 법은 여러가지가 있다.

이 문제를 해결할 때는, bool 변수 flag를 사용했다.

첫 for문은 flag에 true를 대입하고 break 한 뒤, if문에서 flag가 true값일 때 break를 사용한다.

 

다른 방법으로는 함수를 만들어서 break 대신 return 하는 방법이 있다.

break는 가장 가까운 반복문을 나가지만, return은 무조건 함수를 탈출한다.

이 방법을 사용해보니, 코드 길이는 줄으나 시간이 더 많이 들었다.

---

풀이

 

저번 문제를 통해, bfs의 유용함을 확인했다.

이번 문제의 한 노드에서 점점 퍼져나가는 특징 역시 bfs를 사용해야한다.

 

다만, 여러 곳에서 동시에 퍼지는 (입력에서 1이 2개 이상) 경우가 문제이다.

이 부분은 queue의 선입선출(FIFO) 특징을 활용하면 된다.

 

3번째 예제를 보자.

0,0과 3,5 에서 a 배열 값이 1이다.

push_back 해서 0,0 다음 3,5가 들어간다.

그리고 0,0이 확장되어 1,0을 참조한다.

이는 0,0을 pop 하고 조건에 맞는 1,0을 push_back 하는 것과 같다.

확장될 때마다 날짜의 수가 count 되게 하는 ck[nx][my] = ck[n][m]+1; 역시 중요하다.

평소와 달리, 방문하지 않은 ck[i][j]를 -1로 설정했다.

0으로 하면, 답+1을 답으로 얻게 된다.