[C++] BOJ 7569 / BFS (3차원 배열, tuple 사용)

문제 분석

해당 문제는 Z축이 포함된 3차원에서의 BFS를 계산하는 것이다.

 

해결 방법

세로 칸 수를 X, 가로 칸 수를 Y, 높이를 Z 로 하여 3차원 배열으로 접근한다. 

 

코드

#include <iostream>
#include <tuple>
#include <queue>

using namespace std;
int board[101][101][101];
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};
int main() {
    int n,m,h,status,max=1;
    queue<tuple<int,int,int>> q;
    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 >> status;
                board[i][j][k] = status;
                if(status == 1) {
                    q.push({i,j,k});
                }
            }
        }
    }
    while(!q.empty()) {
        tuple<int,int,int> cur = q.front();
        q.pop();
        for(int dir=0;dir<6;dir++) {
            int nx = get<0>(cur) + dx[dir];
            int ny = get<1>(cur) + dy[dir];
            int nz = get<2>(cur) + dz[dir];
            if(nx<0||ny<0||nz<0) continue;
            if(nx>=n||ny>=m||nz>=h) continue;
            if(board[nx][ny][nz] != 0) continue;
            q.push({nx,ny,nz});
            board[nx][ny][nz] = board[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
        }
    }
    for(int k=0;k<h;k++) {
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(board[i][j][k] == 0){
                    cout << -1;
                    return 0;
                }
                max = board[i][j][k] > max ? board[i][j][k] : max;
            }
        }
    }
    cout << max -1;
}

 

- tuple

이 전 포스팅에서 다룬 pair와 같은 개념이지만, pair는 인자를 최대 2개 까지 밖에 만들지 못하지만, tuple은 3개 이상을 만들 수 있다.

#include <tuple>
queue<tuple<int,int,int>> q;
q.push(make_tuple(1,2,3));
q.push({1,2,3});

header 파일은 "tuple" 이다.

make_tuple을 사용하여 값을 넣어줄 수도 있고, { ] 를 사용해서 넣어줄 수 있다.

get<0>(q.front()) 로 1을,

get<1>(q.front()) 로 2를,

get<2>(q.front()) 로 3을 접근할 수 있다.

 

참고 링크

• 3차원 배열
  • https://blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=james_parku&logNo=110168473749
• tuple 사용법
  • https://cocoon1787.tistory.com/408