(cpp) Baekjoon 7576번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색
Baekjoon 7576번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색
예제입력3에 대한 문제풀이
1. 익은 토마토가 있는 칸부터 시작한다. 익은 토마토가 여러개면 동시에 출발해야 최단시간을 달성할 수 있다. 시작큐 = [[1,1][4,6]]를 넣어준다 방문 check는 해당 칸에 며칠째에 도착했는지로 기록한다. check[1][1]=1, check[4][6]=1
2. [1,1]에서 시작했을 때 갈 수 있는 곳은 [2,1]뿐이다.(방문 조건은, map을 벗어나지 않으면서 해당 칸의 state가 0인 경우만 가능하다) [1,1]을 거쳤다가 둘째날에 도착했으니, check[2][1] = check[1][1] + 1 =2이 되고 [2,1]이 새로운 시작큐로 갱신된다. 비슷한 방식으로, [4,6]에서 시작했을 때 갈 수 있는 곳은 [3,6]뿐이며 [4,6]을 거쳤다가 둘째날에 도착으므로 check[3][6] = check[4][6] + 1 = 2이 되고 [3,6]또한 시작큐에 넣어준다.
3. 둘째날의 시작큐는 첫째날에 넣어준 [[2,1] [3,6]]으로 구성되어 있다. 1~2번 과정을 반복한다.
4. 갈 수 있는 곳이 없어 시작큐가 더 이상 채워지지 않으면 종료된다.
5. check박스에 0이 남아있으면 -1출력한다.
6. 0이 없는 경우 체크박스를 구성하는 state중 최대값을 출력한다. 단, 방문일을 1일부터 카운트 시작했으므로 최종 결과는 -1해주어야 한다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
queue<pair<int, int>> q;
int m, n, state, g[1001][1001];
int x_pos[4] = { 0,0, -1, 1 };
int y_pos[4] = { -1,1,0,0 };
int result = 0;
void solution() {
while (!q.empty()) {
int cur_r = q.front().first; // 4
int cur_c = q.front().second;// 6
q.pop(); //q=[]
for (int i = 0; i < 4; i++) {
int next_r = cur_r + x_pos[i]; // 4
int next_c = cur_c + y_pos[i]; // 5
if (0 < next_r && next_r <= n && 0 < next_c && next_c <= m && g[next_r][next_c]==0) {
g[next_r][next_c] = g[cur_r][cur_c] + 1; //몇째날에 들렸는지 기록;
q.push(make_pair(next_r, next_c)); //q=[4,5][3,5]
}
}
}
}
int main() {
cin >> m >> n;
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
cin >> state;
g[i][j] = state;
if (g[i][j] == 1) {
q.push(make_pair(i, j)); // 0번째날 들린 곳 = [4,6]
}
}
}
solution();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == 0) {
cout << -1;
return 0;
}
if (result < g[i][j]) {
result = g[i][j]; //g[i][j]에 저장된 최대값 찾기
}
}
}
cout << result -1;
cout << '\n';
return 0;
}
- 데이터 입력 형식을 구성하는 것이 어려웠음.
- 방문한 곳의 체크를 단순히 ‘방문 했음, 안했음’으로 기록하는 것이 아니라 몇 번째 날에 방문했는지 기록하는 아이디어가 중요했다.
- 다른 그래프 이론에서도 방문 체크를 어떤 걸로 할지 다양하게 생각해보아야 한다.