[코딩테스트 C++] 토마토

오늘의 문제

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

토마토

접근 방식

• 3차원으로된 이전에 풀었던 토마토문제
• 검사 방향이 2 늘어난 것 빼고 풀이 방법은 같다. 각 연산을 잘 정의해주면 된다.
• bfs를 사용한 이유는, bfs를 이용하면 반드시 처음 마주한 상태가 최단거리이기 때문.
• 토마토가 있는 자리를 queue에 push해두면 순차적으로 예쁘계 경로를 탐색한다. 편-안

나의 풀이

#include<iostream>
#include <queue>
using namespace std;
const int MAX = 100;
int m,n,h;
int arr[MAX][MAX][MAX];
int dx[] = {0, 0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 0, -1, 1};
int dz[] = {1, -1, 0, 0, 0, 0};
queue<pair<pair<int, int>, pair<int, int>>> q;

int solution(){
    int depth=0;
    while(!q.empty()){
        depth = q.front().first.first;
        int tz = q.front().first.second;
        int ty = q.front().second.first;
        int tx = q.front().second.second;
        q.pop();
        
        for(int i=0;i<6;i++){
            int mx = tx+dx[i];
            int my = ty+dy[i];
            int mz = tz+dz[i];
            if(mx>=m || mx<0 || my>=n ||  my<0 || mz>=h || mz<0)
                continue;
            if(arr[mz][my][mx] == 0){
                arr[mz][my][mx] = 1;
                q.push(make_pair(make_pair(depth+1, mz), make_pair(my, mx)));
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j = 0;j<n;j++){
            for(int k=0;k<m;k++){
                if(arr[i][j][k] == 0)
                    return -1;
            }
        }
    }
    return depth;
}

다른 풀이

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int board[100][100][100];
int dz[6] = { -1,1,0,0,0,0 };
int dx[6] = { 0,0,-1,1,0,0 };
int dy[6] = { 0,0,0,0,-1,1 };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int m, n, h;
	cin >> m >> n >> h;
	queue<tuple<int,int,int,int>> q;
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cin >> board[k][i][j];
				if (board[k][i][j] == 1) q.push({ k,i,j,0 });
			}
		}
	}
	int mx = 0;
	while (!q.empty()) {
		int cz, cx, cy, cd;
		tie(cz, cx, cy, cd) = q.front(); q.pop();
		for (int i = 0; i < 6; i++) {
			int nz = cz + dz[i], nx = cx + dx[i], ny = cy + dy[i];
			if (nz < 0 || nz >= h || nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (board[nz][nx][ny] == 0) {
				q.push({ nz,nx,ny,cd + 1 });
				board[nz][nx][ny] = 1;
				mx = cd + 1;
			}
		}
	}
	for (int k = 0; k < h; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[k][i][j] == 0) {
					cout << -1;
					return 0;
				}
			}
		}
	}
	cout << mx;

	return 0;
}

배울 점

• 함수로 나누지 않은 점 빼고 방법이 같다