[BaekJoon/백준] 7576번 C++

1697번, 2606번 같은 BFS 유형의 문제였다. BFS 코드의 방향이 다 비슷비슷하다.

처음 queue에 push 하고, visit 처리. 그리고 while문 돌면서 팝 하면서 이 때도 push하고 visit 처리... 반복

 

 

다만 이전 문제들과 다르게 시작 노드가 두개이상 일 수 있어서, 큐를 두개 구현해야하나.. 이런저런 생각을 했지만

옳지 않은 방향으로 갈 뿐이였다 ㅜㅜ..

 

풀이를 검색했고, 어떤 분의 풀이를 보고 느낌이 왔다..

 

생각해보니 시작 노드가 두개라고 해서 큐를 두개 구현할 필요가 없었다.

예를 들면,

1을 큐에 넣고 pop을 한 뒤 child node 2, 3을 넣었을 때와

처음부터 2 3이 각각 시작노드라고 생각해도 구현이 똑같기 때문이였다.

 

이런식으로 문제를 풀게 되었다!

// 생각해보니 큐 하나로 해도 문제가 없다..

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int arr[1001][1001];
bool visit[1001][1001];

int v1[4] = {-1, 0, 1, 0};
int v2[4] = {0, 1, 0, -1};

queue<pair<int, int>> que;


void bfs() {
    
    while(que.empty() == 0) {
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            int xx = v1[i] + x;
            int yy = v2[i] + y;
            
            if(xx >= 0 && xx < N && yy >= 0 && yy < M) {
                if(arr[xx][yy] != -1 && !visit[xx][yy]) {
                    arr[xx][yy] = arr[x][y] + 1;
                    visit[xx][yy] = true;
                    que.push({xx, yy});
                }
            }
        }
    }
    
}

int MAX() {
    int max = -1;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(arr[i][j] == 0) { // 못채운 곳이 있다면
                return -1;
            }
            max = (max < arr[i][j])? arr[i][j]:max;
        }
    }
    if(max == 1) // 모든 토마토가 처음부터 익은상태. 값이 아무것도 늘지 않은 상태.
        return 0;
    
    return max - 1; // 토마토 위치가 1이며, 인접 날짜는 첫날부터 2부터 시작했으므로 하루를 빼줘야 함.
}

int main() {
    int i, j;
    
    
    cin >> M >> N;
    
    for(i = 0; i < N; i++) {
        for(j = 0; j < M; j++) {
            cin >> arr[i][j];
            
            if(arr[i][j] == 1) {
                que.push({i, j});
                visit[i][j] = 1;
            }
        }
    }
    bfs();
    
    cout << MAX();
}

 

설명은 아래 블로그를 참고하면 좋겠다!!

참고 : jdselectron.tistory.com/55