백준 7576 토마토

문제 링크 : https://www.acmicpc.net/problem/7576

※선행해야 할 알고리즘 : BFS/DFS

Algorithm : BFS/DFS 를 활용하여 행렬에서 -1을 제외한 모든 0을 1로 만들 때 걸리는 최단 횟수를 구하여라. (단, 모든 0을 1로 만들지 못할 시엔 -1 출력)

1. 토마토가 익은 index를 입력 시, 1일 때 바로 queue에 삽입한다.

BFS를 실행할 시, 토마토가 익은 구간을 queue에 삽입하여야 한다. 이 때, 모든 index를 입력 후에 1을 찾게 된다면 n*m만큼의 시간복잡도가 추가되기에 복잡도 단축을 위해 입력하면서 바로 queue에 삽입할 수 있도록 한다.

2. 또한, visit 배열을 초기화 할 때 모두 false로 처리하는 것이 아니고 queue에 삽입하면서 true로 바꾸어주고, 토마토가 비어있는(-1이 입력된 index) 구간도 true로 설정해준다. 그 이유는 -1은 BFS 진행 시 들릴 필요가 없기 때문이다.

3. 1~2처럼 visit 배열과 queue를 설정해주었다면 BFS를 진행한다. 진행할 때는 queue에 삽입될 때마다 해당 queue에 대해 count를 세준다.

조금 조심해야 할 부분은 예를 들어, 입력 예제 4번을 본다면

6 4

0 -1 0 0 0 0

-1 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 1

[5][3]의 queue가 실행 될 것이다. 이 때, 모든 BFS가 실행되면

0 -1 1 1 1 1

-1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

이 되면서 count를 출력하게 될 것인데 [0][0]가 익질 못한 상태이다. 따라서 -1을 출력해야 하므로 queue.empty()가 되었을 때 visit 배열을 한 번 더 검사할 필요가 있다.

4. queue를 활용하여 BFS를 진행하면 다음과 같다.

#include<iostream> #include<vector> #include<queue> #include<algorithm> #include<string> using namespace std; typedef struct set { int x; int y; int count; }set; vector<vector<int>> T; queue<set> q; vector<vector<bool>> check; int dx[] = { 1,-1,0,0 }; int dy[] = { 0,0,1,-1 }; int row, col; int bfs(vector < vector<int>> T, queue<set> q, vector<vector<bool>>check) { int sol; while (!q.empty()) { int x = q.front().x; int y = q.front().y; int result = q.front().count; q.pop(); for (int i = 0; i < 4; i++) { int now_x = x + dx[i]; int now_y = y + dy[i]; if (now_x >= 0 && now_x < col && now_y >= 0 && now_y < row  && !check[now_x][now_y] && T[now_x][now_y] == 0) { check[now_x][now_y] = true; q.push({ now_x, now_y, result + 1 }); } } sol = result; } bool ok=false; for (int i = 0; i < check.size(); i++) for (int j = 0; j < check[i].size(); j++) if (check[i][j] == false) ok = true; if (ok) return -1; return sol; } int main() { cin >> row >> col; T.resize(col); check.resize(col); for (int i = 0; i < col; i++) { T[i].resize(row,false); check[i].resize(row); for (int j = 0; j < row; j++) { cin >> T[i][j]; if (T[i][j] == 1) { q.push({ i,j,0 }); check[i][j] = true; } else if (T[i][j] == -1) check[i][j] = true; } } if (q.empty()) cout << -1 << endl; else cout << bfs(T, q, check) << endl; return 0; }