[백준 7576번] 토마토

문제 화면

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

문제 풀이

이 문제는 queue 자료구조를 이용하는 BFS의 대표적인 문제이다. 다른 BFS 문제와 다른 점이 있다면 BFS 중에서 시작점이 여러개인 경우인데 시작이 하나인 경우와 다른 점은 딱히 없는게 처음부터 두 시작점을 큐에 넣어주면 된다. 그리고 토마토가 익은 경우와 안익은 경우와 없는 경우를 분별해서 익은 경우와 없는 경우 방문을 하지 않고 안익은 경우에만 방문을 해서 거리를 표시해준다. 모든 연산이 끝나면 마지막에 이중포문을 돌면서 안익은 토마토가 없는지, 없다면 최대 숫자를 구해서 모든 토마토가 익기까지 몇일이 걸리는지 출력해주면 된다.

제출 코드

#include <iostream>
#include <queue>

using namespace std;

int map[1002][1002];
int vis[1002][1002];
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, dist = 1, maxdist = 0;
    queue<pair<int,int>> q;

    cin >> m >> n;

    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            cin >> map[i][j];
            if(map[i][j]==1){
                q.push({i,j}); // 토마토가 있는 좌표 바로 Q에 넣는다
                vis[i][j] = dist; // 헷갈리지 않게 처음부터 1로 시작
            }
            else if(map[i][j]==-1) vis[i][j] = -1; // 토마토가 없는 건 방문할 필요가 없기에 vis에도 표시해줌
        }
    }
    
    while(!q.empty()) {
        auto cur = q.front(); q.pop();
        dist = vis[cur.first][cur.second] + 1; 
        for(int dis = 0 ; dis < 4 ; dis++) {
            int nx = cur.first + dx[dis];
            int ny = cur.second + dy[dis];
            // 동서남북 좌표 설정
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue; // 범위 벗어났거나
            if(vis[nx][ny]!=0) continue; // 이미 방문한 곳이거나 토마토가 없거나

            q.push({nx, ny});
            vis[nx][ny] = dist;
        }
    }

    // 연산 다 끝나고 안익은 토마토가 있는지(있으면 -1), 없다면 최대 거리는 뭔지 알아내기
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < m ; j++) {
            if(vis[i][j]==0) { // 방문 안했다는 의미 -> 안익은 토마토가 있다!
                cout << -1;
                return 0;
            }
            maxdist = max(maxdist, vis[i][j]);
        }
    }

    cout << maxdist-1;

    return 0;

}

결론

BFS 풀다보니까 확실히 풀 때 감이 빨리오고 코드도 빨라지는 것 같다. 알고리즘은 문제를 많이 푸는게 장땡인거 같다.

출처

• https://blog.encrypted.gg/941?category=773649