BOJ : 7569 토마토2 (C++)

김정욱·2020년 10월 29일
0

Algorithm - 문제

목록 보기
29/249
post-custom-banner

문제

Code

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int board[102][102][102];
int dist[102][102][102];
#define X first
#define Y second
int dir[6][3] = {{0,1,0},{0,0,1},{0,-1,0},{0,0,-1},{1,0,0},{-1,0,0}};
int M, N, H; // M : y , N : x 
bool check()
{
    for(int h=0;h<H;h++)
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                if(board[h][i][j] == 0)
                    return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans=0;
    queue<pair<int,pair<int,int>>> Q;

    cin >> M >> N >> H;
    for(int h=0;h<H;h++)
    {
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin >> board[h][i][j];
                if(board[h][i][j] == 1)
                {
                    dist[h][i][j] = 1;
                    Q.push({h,{i,j}});
                }
            }
        }
    }
    if(check())
    {
        cout << 0;
        return 0;
    }
    while(!Q.empty())
    {
        auto cur = Q.front(); Q.pop();
        for(int d=0;d<6;d++)
        {
            int nh = cur.X + dir[d][0];
            int nx = cur.Y.X + dir[d][1];
            int ny = cur.Y.Y + dir[d][2];
            if(nh<0 || nh>=H || nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(dist[nh][nx][ny] != 0 || board[nh][nx][ny] != 0) continue;
            dist[nh][nx][ny] = dist[cur.X][cur.Y.X][cur.Y.Y] +1;
            board[nh][nx][ny] = 1;
            Q.push({nh,{nx,ny}});
            ans=max(ans,dist[nh][nx][ny]);
        }
    }
    if(check())
        cout << ans -1 ;
    else
        cout << -1;
}
  • 기존 2차원 토마토에서 높이 -1 / 1 일때 까지 총 6좌표를 검사함
  • 6좌표 검사하는 방법
    1) 배열 1개 사용
int dir[6][3] = {{0,1,0},{0,0,1},{0,-1,0},{0,0,-1},{1,0,0},{-1,0,0}};
...
for(int d=0 ; d<6 ; d++)
{
    int nh = cur.X + dir[d][0];
    int nx = cur.Y.X + dir[d][1];
    int ny = cur.Y.Y + dir[d][2];
    ...
}

2) 배열 3개 사용

int dx[6] = { 0,1,0,-1,0,0 };
int dy[6] = { 1,0,-1,0,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
...
for (int i = 0; i < 6; i++)
{
    int nz = cur.Y.Y + dz[i];
    int nx = cur.Y.X + dx[i];
    int ny = cur.X.X + dy[i];
    ...
}
  • fill()을 이용해서 dist를 -1로 3차원 초기화 안되서 그냥 dist의 조건을 바꿈
if(dist[nh][nx][ny] != 0 || board[nh][nx][ny] != 0) continue;
profile
Developer & PhotoGrapher
post-custom-banner

0개의 댓글