반응형
https://www.acmicpc.net/problem/7576
💡 토마토
✅ 문제 풀이
- BFS를 활용하는 문제이다.
- queue를 사용하여 방문해야 할 곳을 pair<int,int> 형태의 좌표를 저장하도록 하였다.
- 먼저 토마토에 대한 2차원 배열을 순회하면서 값이 1이면 그 위치를 q라는 queue에 pair<int,int> 형태로 넣는다.
- 모두 탐색한 후에는 while문으로 q가 빌때까지 bfs를 수행한다.
- q에서 가장 앞에 있는 front의 first와, second를 bfs의 인자로 넘겨준다.
- BFS함수의 동작
1. 인자로 받은 위치를 가지고, 동 서 남 북 방향에 있는 값이 배열의 인덱스 범위에 유효하며, 값이 0인지 확인한다.
2. 위의 조건을 만족한다면 해당 위치의 arr값을 1로 변경해주고, temp라는 이름의 queue에 해당 위치를 pair<int,int> 형태로 넣어준다.
- BFS함수를 돌고 나면 q에서 pop한다.
- 그런다음, 현재 q가 비어있다면, 하루에 익을 수 있는 토마토는 다 익은 것이므로 하루를 카운트 하기 위해 answer를 1 증가시킨다.
- 새로 익어진 토마토에 대한 정보를 가진 temp 있는 위치 정보들을 q에 다 옮겨놓는다.
- 그리고나서 이어지는 다음 while문 동작부터는 다음 날짜에 대한 동작을 진행하는 것이다.
- 그런데, q가 비어지게 되면 temp가 비어있고, 그날이 마지막 날이었더라도 하루가 무조건 더해지게 되기 때문에, 마지막에는 answer에서 1을 뺀 값이 답이된다.
- while문을 모두 수행하고 나면, 갱신된 2차원 배열을 순회하면서, 하나라도 0이 있는 값이 있는지 찾아본다.
- 이는 0이 하나라도 있다면 모든 토마토가 익어질 수 없다는 뜻이므로 -1을 출력하고 프로그램을 종료하기 위함이다.
- 그렇지 않다면 answer-1을 출력하도록 하여, 토마토 판에서 토마토가 다 익는데 걸리는 날을 출력한다.
✏ 코드 전문
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n, m;
vector<vector<int>> arr;
queue<pair<int, int>> q;
queue<pair<int, int>> temp;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int answer = 0;
void bfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n&&ny >= 0 && ny < m&&arr[nx][ny] == 0) {
arr[nx][ny] = 1;
temp.push(pair<int, int>(nx, ny));
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> m >> n;
arr.resize(n,vector<int>(m));
bool end = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 1) {
q.push(pair<int,int>(i, j));
}
}
}
while (!q.empty()) {
bfs(q.front().first, q.front().second);
q.pop();
if (q.empty()) {//한번 돌았음을 의미
answer++;
while(!temp.empty()) {
q.push(pair<int,int>(temp.front().first, temp.front().second));
temp.pop();
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 0) {
cout << -1;
return 0;
}
}
}
cout << answer-1;
return 0;
}
반응형
'CO-TE > 백준' 카테고리의 다른 글
[백준] 2447번 C++ "별 찍기 -10" 풀이 / 재귀, 분할정복, 프렉탈 (0) | 2024.01.24 |
---|---|
[백준] 11729번 C++ "하노이 탑 이동 순서" 풀이 / 재귀호출 (1) | 2024.01.23 |
[백준] 12865번 C++ "평범한 배낭" 풀이 / DP, 동적계획법 (0) | 2024.01.12 |
[백준] 1780번 C++ "종이의 개수" 풀이 / 분할과 정복, 재귀호출 (1) | 2024.01.12 |
[백준] 1149번 C++ "RGB거리" 풀이 / DP, 동적 계획법 (1) | 2024.01.09 |