[백준] 7576 7569 토마토(C++)

7576번: 토마토 (acmicpc.net)

7576번: 토마토

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

---

난이도 : 골드 5

 

해결 방법 :

 

굉장히 오래 걸렸던 문제.... 

일단 배열 입력자체가 보통은 가로, 세로 를 주는데 세로 가로 수를 줘서 

반대로 입력을 해주면 좀더 편하게 풀 수 있다. (이것도 시간 오지게 잡아먹힘 헷갈려서)

 

뭐튼 bfs로 푸는문제인데 처음에 접근을 잘못해서 연결요소의 개수로 접근해 풀었다가 1시간 날렸다

이제 토마토배열에 1인 값이 있는걸 큐에 삽입을 해서 1을 기준으로 bfs를 돌려줘야 함

그래서 배열의 데이터를 입력을 받을 때 미리 1인 아이들을 큐에 삽입 해주면 됨

 

그래서 bfs 돌려서 최단거리구하는 방식으로 해주고

만약에 배열중에 0인 아이가 있다면 다 1로 못만들었다는 뜻이니까 -1을 출력해주면됨

그리고 최단거리는 1부터 시작해서 거리가 +1된 값이 되므로 출력할때만 -1 해주면됨

 

코드 :

 

#include <iostream>
#include <algorithm> 
#include <queue>
#include <vector>
using namespace std;

int n, m, arr[1001][1001], ans = -1;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

queue<pair<int, int>> q;

void bfs() {
    while (!q.empty()) {
        int xx=  q.front().first;
        int yy = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
            if (ny >= 0 && nx >= 0 && nx < n && ny < m && arr[nx][ny] == 0) {
                arr[nx][ny] = arr[xx][yy] + 1;
                q.push(make_pair(nx, ny));                  
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

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

    bfs();

	// 이해를 돕기위한 arr배열 출력 코드 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
           cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0) {
                cout << -1;
                return 0;
            }else {
                ans = max(arr[i][j], ans);
            }
        }
    }

    cout << ans-1;

}

 

 

7569는 기존 토마토 문제에서 z축이 추가된 것이므로, 입력이랑 저장하는 걸 좀만 다르게 해주면 된다.

dz배열을 추가해주고, 3차원 배열로 선언, 큐는 다중페어를 이용하여 선언했다.

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

using namespace std;


int m, n, h, ans, dist[102][102][102];
int dx[] = {0,0,1,-1,0,0};
int dy[] = {1,-1,0,0,0,0};
int dz[] = {0,0,0,0,1,-1};
queue<pair<pair<int,int>, int>> q;

void bfs(){
    while(!q.empty()){
        int xx = q.front().first.first;
        int yy = q.front().first.second;
        int zz = q.front().second;
        q.pop();
        for(int i=0;i<6;i++){
            int nx = xx+dx[i];
            int ny = yy+dy[i];
            int nz = zz+dz[i];
            
            if(nx>=0&&ny>=0&&nz>=0&&nx<n&&ny<m&&nz<h&&dist[nx][ny][nz] == 0){
                dist[nx][ny][nz] = dist[xx][yy][zz] + 1;
                q.push(make_pair(make_pair(nx,ny),nz));
            }
        }
    }
    
}
int main()
{
    cin >> m >> n >> h;
    for(int k=0;k<h;k++){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin >> dist[i][j][k];
                if(dist[i][j][k] == 1){
                    q.push(make_pair(make_pair(i,j),k));
                }
            }
        }
    }
    
    bfs();
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for(int k=0;k<h;k++){
                if (dist[i][j][k] == 0) {
                    cout << -1;
                    return 0;
                }else {
                    ans = max(dist[i][j][k], ans);
                }
            }
            
        }
    }

    cout << ans-1;

    return 0;
}