문제 링크

삼성 코딩테스트 기출 문제: 미지의 공간 탈출 - 코드트리

주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.

코드트리

문제 설명

N*N의 크기의 배열에 M*M*M 크기의 정육면체가 있음. 빈 공간은 0, 장애물은 1, 타임머신(자신)은 2, 정육면체의 위치는 3, 탈출구는 4로 표현됨. 또한 N*N의 배열에는 F개의 확산되는 시간 이상 현상(불)이 존재함. (r_i,c_i)에서 시작해서 매 v_i의 배수 턴마다 방향 d_i로 한 칸씩 확산됨. 해당 미로를 탈출할 수 있는 최소 시간 구하기.

해결 방법

탈출 계산정육면체에 탈출하는 시간동안에는, 움직여주지 않고, 막 탈출 했을 시, 탈출 가능한 위치에 이동할 수 있는 지 확인. 이동할 수 없으면 -1을 반환. 탈출 시에는 queue를 사용하여 초마다 가능한 경로를 저장하고 탈출 시, 걸린 시간을 반환함.

if (t < escape_maze_cnt) continue;
else if (t == escape_maze_cnt) {
    if (arr[smx][smy] == 1) return -1;
    que.push({ smx,smy,t });
}
else {
    queue<tuple<int, int, int>> tmp_que;
    int cx, cy,ct, nx, ny;
    if (que.empty()) return -1;
    while (!que.empty()) {
        tie(cx, cy, ct) = que.front();
        que.pop();
        for (int i = 0;i < 4;i++) {
            nx = cx + dx[i], ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (arr[nx][ny] == 4) {
                t1 = nx, t2 = ny;
                parent_arr[nx][ny] = { cx,cy };
                return ct + 1;
            }
            if (arr[nx][ny] != 0 || visited_arr[nx][ny]) continue;
            visited_arr[nx][ny] = 1;
            parent_arr[nx][ny] = { cx,cy };
            tmp_que.push({ nx,ny,ct + 1 });
        }
    }
    swap(tmp_que, que);
}

불 확산시간이 v의 배수일 때, 확산시키고 위치를 이동.

for (int i = 0;i < f;i++) {
    if (t >= fire[i].v && t % fire[i].v == 0) {
        int nx, ny;
        nx = fire[i].x + dx[fire[i].d], ny = fire[i].y + dy[fire[i].d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (arr[nx][ny] != 0 && arr[nx][ny] != 2) continue;
        arr[nx][ny] = 2;
        fire[i].x += dx[fire[i].d], fire[i].y += dy[fire[i].d];
    }
}

정육면체 탈출정육면체에는 밑면을 제외한 5개의 면이 있고, 각 면마다 이어져있기 때문에, adjust라는 새로운 배열을 만들어서 다른 면으로 갈 때 이어질 수 있도록 하는 배열을 만듦. 5번째 인덱스는 N*N 크기의 배열로 탈출 시의 좌표로 작성하였음.

tuple<int,int,int> adjust[5][11][11][4];
void init() {
    for (int i = 0;i < m;i++) {
        adjust[0][0][i][3] = { 4,i,m - 1 - i };
        adjust[0][i][m - 1][0] = {3,i,0}; 
        adjust[0][m - 1][i][2] = { 5,dsx + (m - 1) - i,dsy + m };
        adjust[0][i][0][1] = { 4,m - 1 - i,m - 1 };
    }

    for (int i = 0;i < m;i++) {
        adjust[1][0][i][3] = { 4,i,0 }; // 좌측의 상단
        adjust[1][i][m - 1][0] = { 2,i,0 }; // 좌측의 우측단
        adjust[1][m - 1][i][2] = { 5,dsx + i,dsy - 1 }; // 좌측의 하단
        adjust[1][i][0][1] = { 3,i,m - 1 }; // 좌측의 좌측단 
    }

    for (int i = 0;i < m;i++) {
        adjust[2][0][i][3] = {4,m-1,i};
        adjust[2][i][m - 1][0] = { 0,i,0 };
        adjust[2][m - 1][i][2] = { 5,dsx+m,dsy+i};
        adjust[2][i][0][1] = { 1,i,m - 1 };
    }

    for (int i = 0;i < m;i++) {
        adjust[3][0][i][3] = { 4,0,m - 1 - i };
        adjust[3][i][m - 1][0] = { 1,i,0 };
        adjust[3][m - 1][i][2] = {5,dsx-1,dsy + (m - 1) - i };
        adjust[3][i][0][1] = {0,i,m-1};
    }

    for (int i = 0;i < m;i++) {
        adjust[4][0][i][3] = { 3,0,m - 1 - i };
        adjust[4][i][m - 1][0] = { 0,0,m - 1 - i };
        adjust[4][m - 1][i][2] = { 2,0,i };
        adjust[4][i][0][1] = { 1,0,i };
    }
}

그리고 BFS를 사용하여 정육면체를 탈출하는 조건을 구함. 탈출조건은 배열로 탈출하고(5번째 인덱스), 해당 위치에 장애물이 없을 시로 판단하였음. 해당 위치는 추후 N*N 배열 탈출을 위해 smx,smy에 저장함. 그리고 parent 배열을 사용하여, 얼마나 걸렸는지 판단 + 디버깅으로 사용하였음.

int visited[5][11][11];
tuple<int, int, int> parent[5][11][11];

int get_maze_path() {
    queue<tuple<int, int, int>> que;
    que.push({ sd,sx,sy });
    visited[sd][sx][sy] = 1;

    int cd, cx, cy, nd, nx, ny;
    bool escape_flag = false;

    while (!que.empty()) {
        tie(cd, cx, cy) = que.front();
        que.pop();

        for (int i = 0;i < 4;i++) {
            nx = cx + dx[i], ny = cy + dy[i]; nd = cd;
            if (nx < 0 || ny < 0 || nx >= m || ny >= m) {
                tie(nd, nx, ny) = adjust[cd][cx][cy][i];
            }
            if (nd == 5 && arr[nx][ny] == 0) {
                smx = nx, smy = ny;
                escape_flag = true;
                break;
            }
            if (nd == 5 && arr[nx][ny]) continue;
            if (visited[nd][nx][ny] || dice[nd][nx][ny]) continue;
            visited[nd][nx][ny] = 1;
            parent[nd][nx][ny] = { cd,cx,cy };
            que.push({ nd,nx,ny });
        }
        if (escape_flag) break;
    }

    if (escape_flag == false) {
        return -1;
    }

    int ret = 1;
    
    int ctd, ctx, cty;
    while (true) {
        if (get<0>(parent[cd][cx][cy]) == sd && get<1>(parent[cd][cx][cy]) == sx && get<2>(parent[cd][cx][cy]) == sy) {
            break;
        }
        ctd = cd, ctx = cx, cty = cy;
        cd = get<0>(parent[ctd][ctx][cty]);
        cx = get<1>(parent[ctd][ctx][cty]);
        cy = get<2>(parent[ctd][ctx][cty]);
        ret++;
    }

    return ret+1;
}

전체 코드

#include <iostream>
#include <tuple>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef struct {
    int x, y;
    int d, v;
}_fire;

int n, m, f;
int arr[21][21];

int dice[5][11][11];
tuple<int,int,int> adjust[5][11][11][4];

_fire fire[11];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

int dsx, dsy; // 미궁의 좌측상단
int sd, sx, sy; // 시작 위치
int smx, smy; // 나와서 시작 위치

void input() {
    cin >> n >> m >> f;

    // 미궁
    bool find_dice = false;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            cin >> arr[i][j];
            if (!find_dice && arr[i][j] == 3) {
                find_dice = true;
                dsx = i, dsy = j;
            }
        }
    }

    // 정육면체
    for (int i = 0;i < 4;i++) {
        for (int j = 0;j < m;j++) {
            for (int k = 0;k < m;k++) {
                cin >> dice[i][j][k];
            }
        }
    }

    for (int i = 0;i < m;i++) {
        for (int j = 0;j < m;j++) {
            cin >> dice[4][i][j];
            if (dice[4][i][j] == 2) {
                sd = 4, sx = i, sy = j;
            }
        }
    }

    int x, y, d, v;
    for (int i = 0;i < f;i++) {
        cin >> x >> y >> d >> v;
        fire[i].x = x, fire[i].y = y, fire[i].d = d, fire[i].v = v;
        arr[x][y] = 2;
    }
}

void init() {
    for (int i = 0;i < m;i++) {
        adjust[0][0][i][3] = { 4,i,m - 1 - i };
        adjust[0][i][m - 1][0] = {3,i,0}; 
        adjust[0][m - 1][i][2] = { 5,dsx + (m - 1) - i,dsy + m };
        adjust[0][i][0][1] = { 4,m - 1 - i,m - 1 };
    }

    for (int i = 0;i < m;i++) {
        adjust[1][0][i][3] = { 4,i,0 }; // 좌측의 상단
        adjust[1][i][m - 1][0] = { 2,i,0 }; // 좌측의 우측단
        adjust[1][m - 1][i][2] = { 5,dsx + i,dsy - 1 }; // 좌측의 하단
        adjust[1][i][0][1] = { 3,i,m - 1 }; // 좌측의 좌측단 
    }

    for (int i = 0;i < m;i++) {
        adjust[2][0][i][3] = {4,m-1,i};
        adjust[2][i][m - 1][0] = { 0,i,0 };
        adjust[2][m - 1][i][2] = { 5,dsx+m,dsy+i};
        adjust[2][i][0][1] = { 1,i,m - 1 };
    }

    for (int i = 0;i < m;i++) {
        adjust[3][0][i][3] = { 4,0,m - 1 - i };
        adjust[3][i][m - 1][0] = { 1,i,0 };
        adjust[3][m - 1][i][2] = {5,dsx-1,dsy + (m - 1) - i };
        adjust[3][i][0][1] = {0,i,m-1};
    }

    for (int i = 0;i < m;i++) {
        adjust[4][0][i][3] = { 3,0,m - 1 - i };
        adjust[4][i][m - 1][0] = { 0,0,m - 1 - i };
        adjust[4][m - 1][i][2] = { 2,0,i };
        adjust[4][i][0][1] = { 1,0,i };
    }
}

int visited[5][11][11];
tuple<int, int, int> parent[5][11][11];

int get_maze_path() {
    queue<tuple<int, int, int>> que;
    que.push({ sd,sx,sy });
    visited[sd][sx][sy] = 1;

    int cd, cx, cy, nd, nx, ny;
    bool escape_flag = false;

    while (!que.empty()) {
        tie(cd, cx, cy) = que.front();
        que.pop();

        for (int i = 0;i < 4;i++) {
            nx = cx + dx[i], ny = cy + dy[i]; nd = cd;
            if (nx < 0 || ny < 0 || nx >= m || ny >= m) {
                tie(nd, nx, ny) = adjust[cd][cx][cy][i];
            }
            if (nd == 5 && arr[nx][ny] == 0) {
                smx = nx, smy = ny;
                escape_flag = true;
                break;
            }
            if (nd == 5 && arr[nx][ny]) continue;
            if (visited[nd][nx][ny] || dice[nd][nx][ny]) continue;
            visited[nd][nx][ny] = 1;
            parent[nd][nx][ny] = { cd,cx,cy };
            que.push({ nd,nx,ny });
        }
        if (escape_flag) break;
    }

    if (escape_flag == false) {
        return -1;
    }

    int ret = 1;
    
    int ctd, ctx, cty;
    while (true) {
        if (get<0>(parent[cd][cx][cy]) == sd && get<1>(parent[cd][cx][cy]) == sx && get<2>(parent[cd][cx][cy]) == sy) {
            break;
        }
        ctd = cd, ctx = cx, cty = cy;
        cd = get<0>(parent[ctd][ctx][cty]);
        cx = get<1>(parent[ctd][ctx][cty]);
        cy = get<2>(parent[ctd][ctx][cty]);
        ret++;
    }

    return ret+1;
}

int visited_arr[21][21];
pair<int, int> parent_arr[21][21];
int t1, t2;

int solve() {
    int escape_maze_cnt = get_maze_path();
    queue<tuple<int, int, int>> que;
    visited_arr[smx][smy] = 1;

    for (int t = 1;;t++) {
        // 불 확산
        for (int i = 0;i < f;i++) {
            if (t >= fire[i].v && t % fire[i].v == 0) {
                int nx, ny;
                nx = fire[i].x + dx[fire[i].d], ny = fire[i].y + dy[fire[i].d];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (arr[nx][ny] != 0 && arr[nx][ny] != 2) continue;
                arr[nx][ny] = 2;
                fire[i].x += dx[fire[i].d], fire[i].y += dy[fire[i].d];
            }
        }
        if (t < escape_maze_cnt) continue;
        else if (t == escape_maze_cnt) {
            if (arr[smx][smy] == 1) return -1;
            que.push({ smx,smy,t });
        }
        else {
            queue<tuple<int, int, int>> tmp_que;
            int cx, cy,ct, nx, ny;
            if (que.empty()) return -1;
            while (!que.empty()) {
                tie(cx, cy, ct) = que.front();
                que.pop();
                for (int i = 0;i < 4;i++) {
                    nx = cx + dx[i], ny = cy + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                    if (arr[nx][ny] == 4) {
                        t1 = nx, t2 = ny;
                        parent_arr[nx][ny] = { cx,cy };
                        return ct + 1;
                    }
                    if (arr[nx][ny] != 0 || visited_arr[nx][ny]) continue;
                    visited_arr[nx][ny] = 1;
                    parent_arr[nx][ny] = { cx,cy };
                    tmp_que.push({ nx,ny,ct + 1 });
                }
            }
            swap(tmp_que, que);
        }
    }
}

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

    //freopen("sample_input.txt", "r", stdin);
    input();
    init();
    cout << solve();

    return 0;
}