[BOJ] 7569번 : 토마토

1. problem :

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std; 
#define X first
#define Y second 
#define Z third 
int board[102][102][102];
int days[102][102][102]; 
int col, row, height; 
int dx[6] = { 1,0,-1,0,0,0 };
int dy[6] = { 0,1,0,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 }; 
bool found = false; 
queue<tuple<int, int, int>> Q; // x,y,z를 담기위해 tuple을 이용; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 

	cin >> col >> row >> height; 
	for (int i = 0; i < height; i++) { // board에 추가하기.
		for (int j = 0; j < row; j++) {
			for (int k = 0; k < col; k++) {
				cin >> board[i][j][k];
			}
		}
	}
	// days값 다 -1로 초기화; 
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < row; j++) {
			fill(days[i][j], days[i][j] + col, -1);
		}
	}
	// 모두 1과 -1로 이루어져있는지 조사  + 1인 값을 모두 Q에 추가; 
	for (int i = 0; i < height; i++) { 
		for (int j = 0; j < row; j++) {
			for (int k = 0; k < col; k++) {
				if (board[i][j][k] == 0) {
					found = true; 
				}
				if (board[i][j][k] == 1) {
					Q.push({ i,j,k }); // height,row,col
					days[i][j][k] = 0;
				}
				
			}
		}
	}
	if (!found) {
		cout << 0 << '\n';
		return 0;
	}
	while (!Q.empty()) {
		tuple<int, int, int> cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 6; dir++) {
			int nx = get<1>(cur) + dx[dir];
			int ny = get<2>(cur) + dy[dir];
			int nz = get<0>(cur) + dz[dir];
			if (nx < 0 || nx >= row || ny < 0 || ny >= col || nz < 0 || nz >= height) continue;
			if ((board[nz][nx][ny] == -1 || board[nz][nx][ny] == 1) || days[nz][nx][ny] >= 1) continue;
			days[nz][nx][ny] = 1 + days[get<0>(cur)][get<1>(cur)][get<2>(cur)];
			Q.push({nz,nx,ny });
		}
	}
	// board값이 0이면서, days값이 -1이 있는지 확인; 있다면 -1 출력; 
	int maxDays = -1;
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < row; j++) {
			for (int k = 0; k < col; k++) {
				if (days[i][j][k] == -1 && board[i][j][k] == 0) {
					cout << -1 << '\n';
					return 0;
				}
				maxDays = max(maxDays, days[i][j][k]);
			}
		}
	}

	cout << maxDays << '\n';
	return 0;
}

Q에 {i, j, k}를 넣기 위해 , Q를 선언할 때 tuple <int, int, int>를 사용하였다. 

 

3. solution 2 :

// Authored by : BueVonHun
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/f3877bee8d3c454482dd3229e4246b49
#include <bits/stdc++.h>
using namespace std;

int dx[6] = {0, 0, 1, -1, 0, 0};
int dy[6] = {1, -1, 0, 0, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
int board[103][103][103];
int dist[103][103][103];
queue<tuple<int, int, int>> Q;
int m, n, h;
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> m >> n >> h;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        int tmp;
        cin >> tmp;
        board[j][k][i] = tmp;
        if (tmp == 1) Q.push({j, k, i});
        if (tmp == 0) dist[j][k][i] = -1;
      }
    }
  }

  while (!Q.empty()) {
    auto cur = Q.front();
    Q.pop();
    int curX, curY, curZ;
    tie(curX, curY, curZ) = cur;
    for (int dir = 0; dir < 6; dir++) {
      int nx = curX + dx[dir];
      int ny = curY + dy[dir];
      int nz = curZ + dz[dir];
      if (nx < 0 || nx >= n || ny < 0 || ny >= m || nz < 0 || nz >= h) continue;
      if (dist[nx][ny][nz] >= 0) continue;
      dist[nx][ny][nz] = dist[curX][curY][curZ] + 1;
      Q.push({nx, ny, nz});
    }
  }

  int ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        if (dist[j][k][i] == -1) {
          cout << -1 << "\n";
          return 0;
        }
        ans = max(ans, dist[j][k][i]);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

< source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/7569.cpp > 

이 코드에서 3차원 배열을 정의하는 방법이 아직 이해가 되지 않는다. 

이 코드에서는 board의 값이 0 일 때 -1로 설정하고 , -1일 때는 건드리지 않는다. 따라서, while 문에서 logic이 더 간단해진다. 외우자!