[삼성기출/C++] 미지의 공간 탈출

이 문제는 필자가 코딩테스트에서 틀렸던 문제이다. 다시 풀어보니, 단 한 부분...에서 잘못되었다는 점을 깨달았다

알고리즘 분류

• 너비 우선 탐색 (BFS)
• 시뮬레이션

문제 설명

https://www.codetree.ai/ko/frequent-problems/problems/escape-unknown-space/description?introductionSetId=&bookmarkId=

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

위와 같은 3차원 공간에서, 시간 이상 현상(빨간색)이 정해진 방향에서 주어진 시간마다 하나씩 전진한다. 타임머신에서 있는 사람이 장애물(파란색)을 피해 탈출구까지 도달할 수 있는지? 도달하면 최단 거리를 리턴해주면 된다.

문제접근

우선 BFS를 어떻게 구현해야 할까? 타임머신에 대한 BFS를 해야할 것이고, 시간 이상 현상에 대한 BFS를 구해야 할 것이다. 순서는 어느 것이 먼저인가? 시간 이상 현상이 있는 곳에 시간 여행자가 이동할 수 없으므로, 시간 이상 현상에 대한 BFS를 먼저 해서 3차원 공간에서 불이 도달하는 구간을 파악한 후에, 시간 여행자에 대한 BFS를 실시해서 해당 칸에 시간 이상 현상보다 먼저 도달할 수 있으면 이동하도록 구현해야 할 것이다.

이렇게 보면 삼성 1번치고 간단해보인다. 하지만, 이 문제에서 가장 중요한 것은, map이 3차원이라는 것이다! 그럼 시간 여행자는 3차원에 해당하는 벽을 이동하면서 탐색해야 하므로, 정육면체 벽끼리, 그리고 벽과 평면을 "이어주는" 것이 중요하다.

3차원 Interface 구현

예를 들면, 정육면체의 윗면의 경우, 오른쪽으로 가면 동쪽 면, 왼쪽으로 가면 서쪽 면, 위쪽으로 가면 북쪽 면, 아래쪽으로 가면 남쪽 면이 될 것이다. 이렇듯 interface를 표시해서 그림을 그리면 다음과 같다.

따라서 dimension으로 표시하면 다음과 같이 총 6개의 차원이 존재하고, 이 차원을 위 그림의 빨간 선을 통해 연결되며, 이 부분을 구현하기만 하면 되는 것이다.

예를 들어 보자. 가장 헷갈리는 부분인 "북쪽"에 대한 이동을 구해보자. 구할때는 동서남북 방면으로 탐색하자.

1. 북쪽에서 동쪽(오른쪽)으로 이동 -> 북쪽에서 오른쪽이면 "서쪽 면" 이다.
2. 북쪽에서 서쪽(왼쪽)으로 이동 -> 북쪽에서 왼쪽이면 "동쪽 면"이다.
3. 북쪽에서 남쪽(아래쪽)으로 이동 -> 북쪽에서 아래쪽이면 "땅 면" 이다.
4. 북쪽에서 위쪽(북쪽)으로 이동 -> 북쪽에서 위쪽이면 "위쪽 면" 이다.

이를 case문으로 나타내면 다음과 같다. newState 는 {dimension, y, x} 로 구성된 구조체이다.

    // 3. 북 -> {서, 동, 땅, 위} 1, 0, 5, 4
    case 3:
      if (x == len)  // 북의 동쪽 -> 서
      {
        newState = {1, y, 0};
      }
      if (x < 0)  // 북의 서쪽 -> 동
      {
        newState = {0, y, len - 1};
      }
      if (y == len)  // 북의 남쪽 -> 땅
      {
        newState = {5, mountain_start_y - 1, mountain_start_x + (len - 1 - x)};
      }
      if (y < 0)  // 북의 북쪽 -> 위
      {
        newState = {4, 0, len - 1 - x};
      }
      break;

여기서 "땅 면"으로 이동할 때가 재미있는데, 땅쪽으로 이동할때는 땅만 보이도록 Top View에서 보인다고 생각해보자. 그럼 북쪽에서 땅으로 이동한다는 건 그림과 같다.

따라서 평면 map 기준 시간의 벽의 위치가 직사각형으로 입력되니깐, 이것의 좌상단 좌표를 mountain_start_y, mountain_start_x 로 저장해 두고, 이걸 이용해 처리해주면 되는 것이다.

Direction을 향한 이동 함수 구현

이 interface를 구현했으므로, 이동 함수를 작성해보자. 이동할때의 핵심은 dimension이 바뀔 때에만 change_dimension함수를 호출해줘서 리턴하면 되는 것이다. 수도 코드는 다음과 같이 작성했다.

우선 두 단계로 갈린다.

1. 0 <= dim <= 4인 경우, 즉 시간의 벽 표면을 따라서 있는 경우
2. dim == 5, 즉 평면에서 이동하는 경우

각각의 경우에 대해 경계를 분석해서 경계에 해당하면 change_dim 함수를 호출해주면 된다. 만약 평면에서 경계값을 넘었다면, 이건 진짜 움직일 수 없는 경계에 해당하므로 움직이지 않는다.

그런데, 여기부터가 핵심이다. 나는 평면에서 시간 이상 현상이 벽으로 "올라가는" 경우에 대해서는 무시했다. 문제의 조건에 없는데 어떻게 무시할 수 있을까?

시간 이상 현상이 평면 -> 벽으로 올라가는 경로를 무시하는 이유

우선 시간 이상 현상이 벽으로 올라간다면 매우 골치아픈 일이 생긴다. 바로 불의 방향이 "바뀌는" 것이다! 예를 들어 평면에서 서쪽으로 이동중이었다면 벽을 타면 위쪽으로 방향이 바뀌고, 위쪽 면에 도달하면 서쪽으로 바뀌고, 다시 또 바뀌고, 그러다가 평면에 다시 오면 또 바뀌고.... 너무 복잡해진다.

하지만 잘 생각해보면, 그럴 필요가 없다!!! 문제의 조건을 다시 한번 보자. 괜히 준 조건이 아니다.

이 조건이 의미하는 것은 무엇일까? 바로, 출구 단 하나를 막아버리면, 입구막기가 되기 때문에 어떤 경로로 벽에서 내려와도, 입구가 막히면 그걸로 끝이라는 거다!

https://namu.wiki/w/%EC%9E%85%EA%B5%AC%EB%A7%89%EA%B8%B0%28%EC%9C%A0%EC%A6%88%EB%A7%B5%29

입구막기(유즈맵)

어린 시절의 추억 입구막기를 생각해보면 명확해진다. 입구만 막아버리면 어떤 경로로 내려와도 평면으로 내려올 수 없는 것이다. 그래서 다음과 같이 쉽게 구현이 가능해진다.

// 해당하는 direction으로 이동했을때의 {ndim, ny, nx} return
// 일반적으로는 y + dy[dir], x + dx[dir] 이나,
// 경계를 벗어난다면 다른 dimension으로 전환 ! <- change_dim()
State go_next(int dim, int y, int x, int dir) {
  int ny = y + dy[dir];
  int nx = x + dx[dir];

  if (dim >= 0 && dim <= 4) {
    if (is_out(dim, ny, nx)) {
      return change_dim(dim, ny, nx);  // 차원 바꾸기
    } else {
      return {dim, ny, nx};  // 그냥 이동
    }
  } else {
    // 벽을 타는 것은 무시-> 못움직이는 걸로 처리
    // 진짜 밖에 나가는 경우는 못움직임
    if (is_out(dim, ny, nx) || land[dim][ny][nx] == 3) {
      return {dim, y, x};  // 입력을 리턴 -> 못움직인다
    } else {
      return {dim, ny, nx};  // 그냥 이동
    }
  }
}

 

시간 지연 현상의 BFS 구하기

이제 BFS를 2번하면 끝이다. 먼저 시간 지연 현상의 bfs다. 그런데 잘 생각해보면, 엄밀하게 말하면 BFS가 아니다. 우리가 구해야하는건 visited 했니 안했니가 아니라, 특정 지점에 시간 지연 현상이 도달하는 최소 시간이다. 그리고 방금 우리는 시간 지연 현상이 벽을 올라가지 않아도 된다는 사실을 증명했으므로 간단하게 vector에 저장된 시간 지연 현상을 장애물, 탈출구, 경계를 만날 때까지 이동시키면 된다.

// 엄밀히는 bfs가 아님
// 장애물, 경계, 탈출구 만나기까지 직진만하면서 최솟값 갱신
// 이때, 땅에서 벽타는 경우는 새로 큐에 넣지 않는다.
// 이유: 벽에서 땅으로 가는 경로는 하나밖에 없으므로
//       입구막기의 효과가 존재하기 때문
void fire_bfs() {
  memset(fire_dist, -1, sizeof(fire_dist));

  queue<Fire> q;
  for (int i = 0; i < f; i++) {
    q.push(fire[i]);
    fire_dist[5][fire[i].y][fire[i].x] = 0;
  }

  while (q.size()) {
    Fire here = q.front();
    q.pop();
    State nextLocation = go_next(5, here.y, here.x, here.d);
    // 경계에 도달하거나, 벽을 타야한다면 종료
    if (here.y == nextLocation.y && here.x == nextLocation.x) continue;
    // 빈공간만 이동 -> 장애물, 탈출구 만나면 종료 (탈출구엔 불 못붙음에
    // 유의)
    if (land[5][nextLocation.y][nextLocation.x] == 0) {
      // 최솟값 경신
      if (fire_dist[5][nextLocation.y][nextLocation.x] == -1) {
        fire_dist[5][nextLocation.y][nextLocation.x] =
          fire_dist[5][here.y][here.x] + here.v;
      }
      fire_dist[5][nextLocation.y][nextLocation.x] =
        min(fire_dist[5][nextLocation.y][nextLocation.x],
            fire_dist[5][here.y][here.x] + here.v);
      // 최솟값 경신과 관계없이 queue에 넣음.
      q.push({nextLocation.y, nextLocation.x, here.d, here.v});
    }
  }
}

내가 코딩테스트에서 틀렸던 부분이 바로 이것같다.. 바로 "탈출구에 불이 붙지 못한다"는 사실이다.. 진짜 문제 조건을 꼼꼼하게 읽어야 한다고 다시 한 번 느꼈다.

시간 여행자의 BFS

이제 interface가 구현이 완료되었으므로, 진짜 BFS를 해주면 된다. 주의할 점은 fire_dist 배열에 저장된 최소 시간보다 빠르게 도달하는 경우만 인정한다는 것이다.

// timeMachine에 대한 진짜 bfs
void machine_bfs() {
  memset(machine_dist, -1, sizeof(machine_dist));

  queue<State> q;
  q.push(timeMachine);
  machine_dist[timeMachine.dim][timeMachine.y][timeMachine.x] = 0;

  while (q.size()) {
    State here = q.front();
    q.pop();
    for (int dir = 0; dir < 4; dir++) {
      State nextLocation = go_next(here.dim, here.y, here.x, dir);
      int ndim = nextLocation.dim;
      int ny = nextLocation.y;
      int nx = nextLocation.x;

      // 장애물은 못지나감
      if (land[ndim][ny][nx] == 1) continue;
      // 방문한 곳 못지나감
      if (machine_dist[ndim][ny][nx] != -1) continue;
      // 불이 먼저 도달한 경우
      if (ndim == 5 && fire_dist[ndim][ny][nx] != -1 &&
          fire_dist[ndim][ny][nx] <= machine_dist[here.dim][here.y][here.x] + 1)
        continue;

      machine_dist[ndim][ny][nx] = machine_dist[here.dim][here.y][here.x] + 1;
      q.push(nextLocation);
    }
  }
}

 

전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void fastIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

typedef struct _State {
  int dim, y, x;
} State;

int land[6][24][24];  // {dim, y, x};

int visited[6][24][24];
int fire_dist[6][24][24];
int machine_dist[6][24][24];
State timeMachine;
State exitPoint;

typedef struct _Fire {
  int y, x, d, v;
} Fire;

Fire fire[14];
int n, m, f;
const int dy[] = {0, 0, 1, -1};  // 동서남북
const int dx[] = {1, -1, 0, 0};  // 동서남북

int mountain_start_y;
int mountain_start_x;

bool is_out(int dim, int y, int x) {
  int len = (dim == 5) ? n : m;
  return (y < 0 || y >= len || x < 0 || x >= len);
}

/// @brief 경계를 벗어날 경우 차원과 좌표를 변환해서 리턴함
/// @param dim 
/// @param y 
/// @param x 
/// @return {dim, y, x} 
State change_dim(int dim, int y, int x) {
  State newState = {-1, -1, -1};
  int len = m;

  // 동 서 남 북 위순으로 탐색하자..

  switch (dim) {
    // 0. 동 -> {북, 남, 땅, 위} 3, 2, 5, 4
    case 0:          // 동서남북 순으로 탐색
      if (x == len)  // 동의 동쪽 -> 북
      {
        newState = {3, y, 0};
      }
      if (x < 0)  // 동의 서쪽 -> 남
      {
        newState = {2, y, len - 1};
      }
      if (y == len)  // 동의 남쪽 -> 땅
      {
        newState = {5, mountain_start_y + (len - 1 - x),
                    mountain_start_x + len};
      }
      if (y < 0)  // 동의 북 -> 위
      {
        newState = {4, len - 1 - x, len - 1};
      }
      break;
    // 1. 서 -> {남, 북, 땅, 위} 2, 3, 5, 4
    case 1:
      if (x == len)  // 서의 동쪽 -> 남
      {
        newState = {2, y, 0};
      }
      if (x < 0)  // 서의 서쪽 -> 북
      {
        newState = {3, y, len - 1};
      }
      if (y == len)  // 서의 남쪽 -> 땅
      {
        newState = {5, mountain_start_y + x, mountain_start_x - 1};
      }
      if (y < 0)  // 서의 북쪽 -> 위
      {
        newState = {4, x, 0};
      }
      break;
    // 2. 남 -> {동, 서, 땅, 북} 0, 1, 5, 4
    case 2:
      if (x == len)  // 남의 동쪽 -> 동
      {
        newState = {0, y, 0};
      }
      if (x < 0)  // 남의 서쪽 -> 서
      {
        newState = {1, y, len - 1};
      }
      if (y == len)  // 남의 남쪽 -> 땅
      {
        newState = {5, mountain_start_y + len, mountain_start_x + x};
      }
      if (y < 0)  // 남의 북쪽 -> 위
      {
        newState = {4, len - 1, x};
      }
      break;
    // 3. 북 -> {서, 동, 땅, 위} 1, 0, 5, 4
    case 3:
      if (x == len)  // 북의 동쪽 -> 서
      {
        newState = {1, y, 0};
      }
      if (x < 0)  // 북의 서쪽 -> 동
      {
        newState = {0, y, len - 1};
      }
      if (y == len)  // 북의 남쪽 -> 땅
      {
        newState = {5, mountain_start_y - 1, mountain_start_x + (len - 1 - x)};
      }
      if (y < 0)  // 북의 북쪽 -> 위
      {
        newState = {4, 0, len - 1 - x};
      }
      break;
    // 4. 위 -> {동, 서, 남, 북} 0 1 2 3
    case 4:
      if (x == len)  // 위의 동쪽 -> 동
      {
        newState = {0, 0, len - 1 - y};
      }
      if (x < 0)  // 위의 서쪽 -> 서
      {
        newState = {1, 0, y};
      }
      if (y == len)  // 위의 남쪽 -> 남
      {
        newState = {2, 0, x};
      }
      if (y < 0)  // 위의 북쪽 -> 북
      {
        newState = {3, 0, len - 1 - x};
      }
      break;
    default:
      break;
  }

  return newState;
}

// 해당하는 direction으로 이동했을때의 {ndim, ny, nx} return
// 일반적으로는 y + dy[dir], x + dx[dir] 이나,
// 경계를 벗어난다면 다른 dimension으로 전환 ! <- change_dim()
State go_next(int dim, int y, int x, int dir) {
  int ny = y + dy[dir];
  int nx = x + dx[dir];

  if (dim >= 0 && dim <= 4) {
    if (is_out(dim, ny, nx)) {
      return change_dim(dim, ny, nx);  // 차원 바꾸기
    } else {
      return {dim, ny, nx};  // 그냥 이동
    }
  } else {
    // 벽을 타는 것은 무시-> 못움직이는 걸로 처리
    // 진짜 밖에 나가는 경우는 못움직임
    if (is_out(dim, ny, nx) || land[dim][ny][nx] == 3) {
      return {dim, y, x};  // 입력을 리턴 -> 못움직인다
    } else {
      return {dim, ny, nx};  // 그냥 이동
    }
  }
}

// 엄밀히는 bfs가 아님
// 장애물, 경계, 탈출구 만나기까지 직진만하면서 최솟값 갱신
// 이때, 땅에서 벽타는 경우는 새로 큐에 넣지 않는다.
// 이유: 벽에서 땅으로 가는 경로는 하나밖에 없으므로
//       입구막기의 효과가 존재하기 때문
void fire_bfs() {
  memset(fire_dist, -1, sizeof(fire_dist));

  queue<Fire> q;
  for (int i = 0; i < f; i++) {
    q.push(fire[i]);
    fire_dist[5][fire[i].y][fire[i].x] = 0;
  }

  while (q.size()) {
    Fire here = q.front();
    q.pop();
    State nextLocation = go_next(5, here.y, here.x, here.d);
    // 경계에 도달하거나, 벽을 타야한다면 종료
    if (here.y == nextLocation.y && here.x == nextLocation.x) continue;
    // 빈공간만 이동 -> 장애물, 탈출구 만나면 종료 (탈출구엔 불 못붙음에
    // 유의)
    if (land[5][nextLocation.y][nextLocation.x] == 0) {
      // 최솟값 경신
      if (fire_dist[5][nextLocation.y][nextLocation.x] == -1) {
        fire_dist[5][nextLocation.y][nextLocation.x] =
          fire_dist[5][here.y][here.x] + here.v;
      }
      fire_dist[5][nextLocation.y][nextLocation.x] =
        min(fire_dist[5][nextLocation.y][nextLocation.x],
            fire_dist[5][here.y][here.x] + here.v);
      // 최솟값 경신과 관계없이 queue에 넣음.
      q.push({nextLocation.y, nextLocation.x, here.d, here.v});
    }
  }
}

// timeMachine에 대한 진짜 bfs
void machine_bfs() {
  memset(machine_dist, -1, sizeof(machine_dist));

  queue<State> q;
  q.push(timeMachine);
  machine_dist[timeMachine.dim][timeMachine.y][timeMachine.x] = 0;

  while (q.size()) {
    State here = q.front();
    q.pop();
    for (int dir = 0; dir < 4; dir++) {
      State nextLocation = go_next(here.dim, here.y, here.x, dir);
      int ndim = nextLocation.dim;
      int ny = nextLocation.y;
      int nx = nextLocation.x;

      // 장애물은 못지나감
      if (land[ndim][ny][nx] == 1) continue;
      // 방문한 곳 못지나감
      if (machine_dist[ndim][ny][nx] != -1) continue;
      // 불이 먼저 도달한 경우
      if (ndim == 5 && fire_dist[ndim][ny][nx] != -1 &&
          fire_dist[ndim][ny][nx] <= machine_dist[here.dim][here.y][here.x] + 1)
        continue;

      machine_dist[ndim][ny][nx] = machine_dist[here.dim][here.y][here.x] + 1;
      q.push(nextLocation);
    }
  }
}

void print() {
  cout << timeMachine.dim << " : " << timeMachine.y << " : " << timeMachine.x
       << endl;
  cout << "fire : " << endl;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << fire_dist[5][i][j] << ' ';
    }
    cout << endl;
  }
  cout << endl;

  cout << "동 서 남 북 위 평면" << endl;
  for (int k = 0; k < 5; k++) {
    cout << " :  : " << k << " :  : " << endl;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        cout << machine_dist[k][i][j] << ' ';
      }
      cout << endl;
    }
    cout << endl;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << machine_dist[5][i][j] << ' ';
    }
    cout << endl;
  }
}

int main() {
  cin >> n >> m >> f;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> land[5][i][j];
      if (land[5][i][j] == 4) {
        exitPoint = {5, i, j};
      }
    }
  }
  for (int dim = 0; dim < 5; dim++) {
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        cin >> land[dim][i][j];
        if (land[dim][i][j] == 2) {
          timeMachine = {dim, i, j};
        }
      }
    }
  }
  for (int i = 0; i < f; i++) {
    cin >> fire[i].y >> fire[i].x >> fire[i].d >> fire[i].v;
  }

  int flag = false;
  for (int i = 0; i < n; i++) {
    if (flag) break;
    for (int j = 0; j < n; j++) {
      if (land[5][i][j] == 3) {
        mountain_start_y = i;
        mountain_start_x = j;
        flag = true;
        break;
      }
    }
  }

  memset(machine_dist, -1, sizeof(machine_dist));
  fire_bfs();
  machine_bfs();
  // print();
  cout << machine_dist[exitPoint.dim][exitPoint.y][exitPoint.x] << endl;
}

 

Inteface 구현 부분에 주의한다면 나머지는 쉬운 BFS 문제다.