[백준 : 7576] 토마토 [C++] (BFS)

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

 

---

오랜만에 방학?종강?! 기념 문풀..

이 문제는 오랫동앤 시도했지만 틀렸음에 박아두고 보지 않던 친구인데, 막 dfs를 배웠을 때 dfs로 할 수 있을 줄 알고 dfs로 풀었따가 과감하게 틀린 문제이다.. bfs로 푸는게 정배인 문제!

최단 거리 문제의 일종이라고 보면 됨!

---

 

 

간단하게 말해서, 최단거리 구하는 (미로 찾기) 형태의 BFS이되 출발점이 여러개일 수 있음! 이 점만 유의해서 풀어주면 되는 미로찾기 형 BFS 문제이다.

---

시간 초과 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N,M;

int map[1001][1001];
int visited[1001][1001];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

vector<int> v;

int safe(int x, int y){
    if(x>=0 && x<N && y>=0 && y<M){
        return 1;
    }
    return 0;
}

void print(){
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << visited[i][j] << ' ';
        }
        cout << '\n';
    }
}

void bfs(int sx, int sy){

    queue<pair<int,int>> que;

    que.push(make_pair(sx,sy));
    visited[sx][sy] = 1;
    
    while(que.size()>0){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();

        for(int i = 0; i<4; i++){
            if (safe(x+dx[i],y+dy[i]) && map[x+dx[i]][y+dy[i]] == 0 && (!visited[x+dx[i]][y+dy[i]] || visited[x+dx[i]][y+dy[i]] > visited[x][y]+1)){
                que.push(make_pair(x+dx[i],y+dy[i]));
                visited[x+dx[i]][y+dy[i]] = visited[x][y]+1;
            }
        }

    }
}

int main(void){

    cin >> M >> N;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }

    int ans = 0;

    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(map[i][j] == 1){
                bfs(i,j);
            }
        }
    }

    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(visited[i][j]==0 && map[i][j] == 0){
                cout << -1;
                return 0;
            }
            if(visited[i][j]>ans){
                ans = visited[i][j];
            }
        }
    }

    cout << ans-1 << '\n';
}

 

나는 모든 1에서 bfs를 각각 진행하고, 만약 visited가 방문되지 않았거나 이미 구해진 최단거리의 값보다 작으면(다른 토마토 기준으로 이미 익을 수 있지만, 더 가까운 토마토에 의해 익을 수 있을 때) 갱신하는 형태로 구현했으나 44퍼 즈음에서 시간초과가 났다.

if (safe(x+dx[i],y+dy[i]) && map[x+dx[i]][y+dy[i]] == 0 && (!visited[x+dx[i]][y+dy[i]] || visited[x+dx[i]][y+dy[i]] > visited[x][y]+1)){
                que.push(make_pair(x+dx[i],y+dy[i]));
                visited[x+dx[i]][y+dy[i]] = visited[x][y]+1;

 

이 부분!

그래서 질문 게시판에서 힌트를 보니, 큐에 각각의 노드가 번갈아가며 들어갈 수 있게 하라는 말을 들었따.. 즉 이미 익은 토마토의 노드가 번갈아가면서 들어갈 수 있게 하라는 뜻! 와 이런 겁나 간단하고 천재같은 방법이ㅠㅠ

---

정답 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N,M;

int map[1001][1001];
int visited[1001][1001];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

vector<int> v;

int safe(int x, int y){
    if(x>=0 && x<N && y>=0 && y<M){
        return 1;
    }
    return 0;
}

void print(){
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << visited[i][j] << ' ';
        }
        cout << '\n';
    }
}

void bfs(){

    queue<pair<int,int>> que;

    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(map[i][j] == 1){
                que.push(make_pair(i,j)); // 처음 1인 토마토의 위치를 바로 큐에 push
                visited[i][j] = 1;
            }
        }
    }
    
    while(que.size()>0){ // 우리가 아는 평범한 스타일의 bfs
        int x = que.front().first;
        int y = que.front().second;
        que.pop();

        for(int i = 0; i<4; i++){
            if (safe(x+dx[i],y+dy[i]) && map[x+dx[i]][y+dy[i]] == 0 && !visited[x+dx[i]][y+dy[i]]){
                que.push(make_pair(x+dx[i],y+dy[i]));
                visited[x+dx[i]][y+dy[i]] = visited[x][y]+1;
            }
        }

    }
}

int main(void){

    cin >> M >> N;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }

    int ans = 0;

    bfs();

    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(visited[i][j]==0 && map[i][j] == 0){
                cout << -1;
                return 0;
            }
            if(visited[i][j]>ans){
                ans = visited[i][j];
            }
        }
    }

    cout << ans-1 << '\n';
}

 

bfs를 처음 익어있던 모든 토마토마다 하는 것이 아닌, 1인 토마토(시작 시점 익어있던 토마토)가 나오면 바로 큐에 넣어줌으로서 각각의 bfs가 자동으로 번갈아가면서 수행되게 했다! 큐의 특징 (FIFO)의 개념을 잊지 않아야 한다는 것을 다시 한 번 느끼게 됐다. 괜히 어렵게 생각하지 말기~