[백준 7576] 토마토

# 문제 링크

www.acmicpc.net/problem/7576

7576번: 토마토

 

쉽게 생각했다가 엄청 고생한 문제다. 1로 표시된 익은 토마토부터 최단거리 구하는거니까 BFS 로 구하면 되겠네~ 했다. 그래서 배열을 입력 받은 후 for 문 돌려가며 1을 찾아서 DFS를 돌렸고, 가장 작은 수로 배열을 채웠다. 테스트 케이스를 돌렸을 때는 다 맞았는데, 제출을 하면 계속 틀렸다고 나왔다. 뭐가 틀린지도 모르고 계속 싸매다가 결국 구글링을 했다. 

바로 속이 싸악 내려갔다.

 

속이 싸악 내려가노....

 

이 문제 해결 포인트는 배열을 입력받으면서 1이 나오면 큐에 push 를 해주는 것이다. 그리고 큐에 입력된 1의 좌표부터 BFS를 해주면서 최단거리를 찾으면 끝! 하.. 진짜 속 시원한 풀이... 참고 블로그는 하단에 정리해두었다.

 

BFS 순서를 출력하면 다음과 같다.

 

BFS 순서

 

# 제출 코드

 

# include <iostream>
# include <queue>
# include <cstring>
# define MAXN 1000
using namespace std;

int xd[] = { 1, -1, 0, 0 }; // 상하좌우 이동 좌표  
int yd[] = { 0, 0, 1, -1 }; //  
int X; // 가로 칸 수  
int Y; // 세로 칸 수  
int map[MAXN + 1][MAXN + 1]; // 토마토 상자 
int m; // 안익은 토마토 개수
queue<pair<int, int>> q;

void Input() {
	cin >> X >> Y;
	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) { q.push({ i, j }); } // 1 일때 큐에 넣어주기 
		}
	}
}
bool isValid(int y, int x) {
	return (y > 0 && y <= Y && x > 0 && x <= X);
}
int BFS() {
	int max = 1;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + yd[i];
			int nx = x + xd[i];
			if (isValid(ny, nx) == false) continue; // 범위 확인  
			if (map[ny][nx] == 0) { // 안익은 토마토일 때 
				map[ny][nx] = map[y][x] + 1;
				if (map[ny][nx] > max) max = map[ny][nx];
				q.push({ ny, nx });
			}
		}
	}
	return max - 1;
}
bool All_ripe() {
	for (int i = 1; i <= Y; i++) {
		for (int j = 1; j <= X; j++) {
			if (map[i][j] == 0) { // 방문 안한 토마토 
				return false;
			}
		}
	}
	return true;
}
int Solve() {
	int sol = BFS();
	return ((All_ripe() == true) ? sol : -1 );
}
int main() {
	Input();
	cout << Solve();
	return 0;
}

 

 

# 참고 블로그

 

jdselectron.tistory.com/55

[백준 7576, c++] 토마토(bfs)

감사하다고 댓글도 남겼다.. 다시 한 번  감사드립니다~!