[C++] 7576 토마토

C++ / 골5 / 그래프, BFS 너비우선탐색

https://www.acmicpc.net/problem/7576

 

재귀를 써서 복잡하고 비효율적으로 풀다가 정석 BFS 풀이를 공부하고 다시 시도했다.

 

날짜를 어떻게 올려야할 지 고민하다가 큐에 좌표라는 pair와 날짜를 또 한번 pair 처리하여 함께 넣는 방식으로 진행했다.

push를 할 때 두 번째 대괄호를 자꾸 까먹어서 오류 찾기에 애를 먹기도 했다.

 

bfs를 간략하게 살펴보자면,

입력 받은 이차원 배열을 돌면서 익은 토마토가 있는 좌표를 큐에 day 0과 함께 넣는다. 이때, 원래 익어 있던 토마토들도 방문한 것이므로 해당 좌표에서의 vis를 1로 바꿔주는 것을 잊지 않는다.

for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if (arr[i][j] == 1){
                q.push({{i, j}, day});
                vis[i][j] = 1;
            }
        }
    }

 

그리고 bfs 함수를 돌린다. 큐에서 맨 앞에 있는 좌표를 cur(현재 좌표)에 저장하고 해당 좌표에서 상, 하, 좌, 우의 좌표를 탐색하여 큐에 넣는다. 이때 여기서 탐색하여 익은 토마토는 하루가 지난 다음날 익는 것이므로 현재의 day에 1을 더한 값을 좌표와 함께 큐에 넣는다. 또한 인덱스 초과가 나지 않도록 인덱스의 범위와, 썩은 토마토 여부, 이미 방문한 곳인지의 여부를 검사하여 큐에 넣을 지 말 지를 결정한다.

void bfs(){
    while(!q.empty()){
        pair<int, int> cur = q.front().X;
        day = q.front().Y + 1;
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == -1 || vis[nx][ny] == 1) {
                continue;
            }
            if (vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                q.push({{nx, ny}, day});
            }
        }
    }
}

 

그렇게 큐가 완전히 빌 때 까지 while문을 돌고 나간 후에, 썩은 토마토가 아닌 것들 중에 아직 방문하지 않은 게 있다면 토마토가 전부 익는 데 실패한 것이므로 -1을 출력한다. 그렇지 않다면 정상적으로 날짜 수를 출력한다.

for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (vis[i][j] == 0 && arr[i][j] != -1) {
                fail = true;
            }
        }
    }

    if (fail)   cout << -1;
    else    cout << day;

 

다음은 전체 코드이다. 

#include <iostream>
#include <queue>
using namespace std;
#define X first
#define Y second

int m, n, day = -1;
bool fail = false;
int arr[1001][1001] = {0, };
int vis[1001][1001] = {0, };
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<pair<int, int>, int>> q;

void bfs(){
    while(!q.empty()){
        pair<int, int> cur = q.front().X;
        day = q.front().Y + 1;
        q.pop();
        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == -1 || vis[nx][ny] == 1) {
                continue;
            }
            if (vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                q.push({{nx, ny}, day});
            }
        }
    }
}

int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < m; j++){
            cin >> arr[i][j];
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if (arr[i][j] == 1){
                q.push({{i, j}, day});
                vis[i][j] = 1;
            }
        }
    }
    bfs();

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if (vis[i][j] == 0 && arr[i][j] != -1) {
                fail = true;
            }
        }
    }

    if (fail)   cout << -1;
    else    cout << day;
}