수병아... 니가 밉다... (미지의 공간 탈출 c++)

삼성 SW 역량테스트 2024 하반기 오전 1번 문제 복기입니다.

 

문제는 아래 링크에서 보실 수 있습니다.

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

다시는 이런 문제를 틀리지 않기 위해 복기 하였습니다... 🙃

빡센 구현 문제 입니다. 산 부분을 어떻게 처리하느냐가 핵심입니다. 

 

 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
 
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0), cin.tie(0)
#define MAXN 20
#define MAXM 20
#define MAXF 400
#define MAXP 6 * MAXF
#define INF 1e9;
 
void input();
void parsingGraph();
void initializingGraph();
void bfsAndCalculate();
 
int spaceMap[MAXN + 10][MAXN + 10];
int spaceMapCellId[MAXN + 10][MAXN + 10];
int timeWall[6][MAXM + 10][MAXM + 10];
int timeWallCellId[6][MAXM + 10][MAXM + 10];
 
struct AbnormalTimeEvent {
  int xpos, ypos, direction, cycle, alive;
};
 
AbnormalTimeEvent events[MAXF + 10];
vector<vector<int> > graph;
 
int dist[MAXP];
int N, M, E;
 
int main() {
  FASTIO;
  input();
  parsingGraph();
  initializingGraph();
  bfsAndCalculate();
  return 0;
}
 
void input() {
  cin >> N >> M >> E;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> spaceMap[i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[0][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[2][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[1][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[3][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[4][i][j];
    }
  }
 
  for (int i = 1; i <= E; i++) {
    cin >> events[i].xpos >> events[i].ypos >> events[i].direction >>
        events[i].cycle;
    if (events[i].direction == 1)
      events[i].direction = 2;
    else if (events[i].direction == 2)
      events[i].direction = 1;
 
    events[i].alive = 1;
  }
}
 
void parsingGraph() {
  int cnt = 0;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] != 3) {
        cnt++;
        spaceMapCellId[i][j] = cnt;
      }
    }
  }
 
  for (int t = 0; t < 5; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        cnt++;
        timeWallCellId[t][i][j] = cnt;
      }
    }
  }
 
  graph = vector<vector<int> >(cnt + 1, vector<int>(4, -1));
 
  int dx[4] = {0, 1, 0, -1};
  int dy[4] = {1, 0, -1, 0};
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] != 3) {
        int idx = spaceMapCellId[i][j];
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
 
          if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
          if (spaceMap[nx][ny] == 3) continue;
 
          graph[idx][k] = spaceMapCellId[nx][ny];
        }
      }
    }
  }
 
  for (int t = 0; t < 4; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        int idx = timeWallCellId[t][i][j];
 
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
 
          if (nx < 0 || nx >= M) continue;
 
          if (ny < 0) {
            graph[idx][k] = timeWallCellId[(t + 1) % 4][nx][M - 1];
          }
 
          else if (ny >= M) {
            graph[idx][k] = timeWallCellId[(t + 3) % 4][nx][0];
          }
 
          else {
            graph[idx][k] = timeWallCellId[t][nx][ny];
          }
        }
      }
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      int idx = timeWallCellId[4][i][j];
 
      for (int k = 0; k < 4; k++) {
        int nx = i + dx[k];
        int ny = j + dy[k];
 
        if (nx < 0 || ny < 0 || nx >= M || ny >= M) continue;
 
        graph[idx][k] = timeWallCellId[4][nx][ny];
      }
    }
  }
 
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][i][M - 1];
    int idy = timeWallCellId[0][0][M - 1 - i];
    graph[idx][0] = idy;
    graph[idy][3] = idx;
  }
 
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][M - 1][i];
    int idy = timeWallCellId[1][0][i];
    graph[idx][1] = idy;
    graph[idy][3] = idx;
  }
 
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][i][0];
    int idy = timeWallCellId[2][0][i];
    graph[idx][2] = idy;
    graph[idy][3] = idx;
  }
 
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][0][i];
    int idy = timeWallCellId[3][0][M - 1 - i];
    graph[idx][3] = idy;
    graph[idy][3] = idx;
  }
 
  int timewallStartx = -1;
  int timewallStarty = -1;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 3) {
        timewallStartx = i;
        timewallStarty = j;
        break;
      }
    }
    if (timewallStartx != -1) break;
  }
 
  if (timewallStarty + M < N) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[0][M - 1][i];
      int idy =
          spaceMapCellId[timewallStartx + (M - 1) - i][timewallStarty + M];
      graph[idx][1] = idy;
      graph[idy][2] = idx;
    }
  }
 
  if (timewallStartx + M < N) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[1][M - 1][i];
      int idy = spaceMapCellId[timewallStartx + M][timewallStarty + i];
      graph[idx][1] = idy;
      graph[idy][3] = idx;
    }
  }
 
  if (timewallStarty > 0) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[2][M - 1][i];
      int idy = spaceMapCellId[timewallStartx + i][timewallStarty - 1];
      graph[idx][1] = idy;
      graph[idy][0] = idx;
    }
  }
 
  if (timewallStartx > 0) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[3][M - 1][i];
      int idy =
          spaceMapCellId[timewallStartx - 1][timewallStarty + (M - 1) - i];
      graph[idx][1] = idy;
      graph[idy][1] = idx;
    }
  }
 
  return;
}
 
void initializingGraph() {
  fill(dist, dist + (N * N) + 4 * (M * M) + 1, -1);
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 3) continue;
      if (spaceMap[i][j] == 1) {
        int idx = spaceMapCellId[i][j];
        dist[idx] = INF;
      }
    }
  }
 
  for (int i = 1; i <= E; i++) {
    int x = events[i].xpos;
    int y = events[i].ypos;
    int idx = spaceMapCellId[x][y];
    dist[idx] = INF;
  }
 
  for (int t = 0; t < 5; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        if (timeWall[t][i][j] == 1) {
          int idx = timeWallCellId[t][i][j];
          dist[idx] = INF;
        }
      }
    }
  }
}
 
void bfsAndCalculate() {
  queue<int> q;
 
  int cellStart = -1;
  int cellEnd = -1;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 4) {
        cellEnd = spaceMapCellId[i][j];
        break;
      }
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if (timeWall[4][i][j] == 2) {
        cellStart = timeWallCellId[4][i][j];
        break;
      }
    }
  }
 
  q.push(cellStart);
  dist[cellStart] = 0;
 
  for (int runs = 1;; runs++) {
    for (int i = 1; i <= E; i++) {
      if (!events[i].alive) continue;
      if (runs % events[i].cycle) continue;
 
      int nx = events[i].xpos, ny = events[i].ypos;
 
      if (events[i].direction == 0) {
        ny += (runs / events[i].cycle);
      } else if (events[i].direction == 1) {
        nx += (runs / events[i].cycle);
      } else if (events[i].direction == 2) {
        ny -= (runs / events[i].cycle);
      } else {
        nx -= (runs / events[i].cycle);
      }
 
      if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
        events[i].alive = 0;
        continue;
      }
 
      if (spaceMap[nx][ny]) {
        events[i].alive = 0;
        continue;
      }
 
      int idx = spaceMapCellId[nx][ny];
      dist[idx] = INF;
    }
 
    vector<int> nextCells;
 
    while (!q.empty()) {
      int idx = q.front();
      q.pop();
 
      for (int i = 0; i < 4; i++) {
        int idy = graph[idx][i];
        if (idy == -1) continue;
        if (dist[idy] != -1) continue;
        dist[idy] = runs;
        nextCells.push_back(idy);
      }
    }
    int nextCellsSize = nextCells.size();
 
    if (!nextCellsSize) {
      break;
    }
 
    for (int i = 0; i < nextCellsSize; i++) {
      q.push(nextCells[i]);
    }
 
    if (dist[cellEnd] != -1) {
      break;
    }
  }
 
  cout << dist[cellEnd];
}

 

#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
 
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0), cin.tie(0)
#define MAXN 20
#define MAXM 20
#define MAXF 400
#define MAXP 6 * MAXF
#define INF 1e9;
 
void input();
void parsingGraph();
void initializingGraph();
void bfsAndCalculate();
 
// spaceMap - 미지의 공간의 평면도
// spaceMapCellId - 평면도의 각 셀에 대응하는 그래프 정점의 번호를 저장하는 배열
// timeWall - 시간의 벽의 단면도
// timeWallCellId - 시간의 벽의 단면도의 각 셀에 대응하는 그래프 정점의 번호를
// 저장하는 배열
int spaceMap[MAXN + 10][MAXN + 10];
int spaceMapCellId[MAXN + 10][MAXN + 10];
int timeWall[6][MAXM + 10][MAXM + 10];
int timeWallCellId[6][MAXM + 10][MAXM + 10];
 
// 시간 이상 현상에 대한 정보를 저장할 구조체
// 시간 이상 현상이 시작점의 행번호, 열번호, 방향, 확장 주기, 시간 이상 현상의
// 진행여부를 차례로 저장합니다
struct AbnormalTimeEvent {
  int xpos, ypos, direction, cycle, alive;
};
 
AbnormalTimeEvent events[MAXF + 10];
vector<vector<int> > graph;
 
int dist[MAXP];
int N, M, E;
 
int main() {
  FASTIO;
  input();
  parsingGraph();
  initializingGraph();
  bfsAndCalculate();
  return 0;
}
 
void input() {
  cin >> N >> M >> E;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> spaceMap[i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[0][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[2][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[1][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[3][i][j];
    }
  }
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      cin >> timeWall[4][i][j];
    }
  }
 
  for (int i = 1; i <= E; i++) {
    cin >> events[i].xpos >> events[i].ypos >> events[i].direction >>
        events[i].cycle;
    if (events[i].direction == 1)
      events[i].direction = 2;
    else if (events[i].direction == 2)
      events[i].direction = 1;
 
    events[i].alive = 1;
  }
}
 
// 모든 Cell ID에 셀 번호를 부여.
void parsingGraph() {
  int cnt = 0;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] != 3) {
        cnt++;
        spaceMapCellId[i][j] = cnt;
      }
    }
  }
 
  // 단면도의 동쪽, 남쪽, 서쪽, 북쪽, 위쪽 순으로 순회. 번호 지정
  for (int t = 0; t < 5; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        cnt++;
        timeWallCellId[t][i][j] = cnt;
      }
    }
  }
 
  // 부여한 번호의 정점들로 구성된 그래프
  // 정점의 번호에 대응되는 셀과 인접한 셀의 번호를 가지는 정점과 간선 연결
  // 최대 4개의 정점과 연결될 수 있습니다 평면도(단면도)에서,
  // 오른쪽으로 인접한 경우 0, 아래쪽으로 인접한 경우 1, 왼쪽으로 인접한 경우 2,
  // 위쪽으로 인접한 경우 3의 인덱스에 저장합니다
  graph = vector<vector<int> >(cnt + 1, vector<int>(4, -1));
 
  int dx[4] = {0, 1, 0, -1};
  int dy[4] = {1, 0, -1, 0};
 
  // 평면도에 속하는 셀에 대응되는 번호의 정점 쌍에 대한 간선
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] != 3) {
        int idx = spaceMapCellId[i][j];
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
 
          if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
          if (spaceMap[nx][ny] == 3) continue;
 
          graph[idx][k] = spaceMapCellId[nx][ny];
        }
      }
    }
  }
 
  // 단면도의 동쪽, 남쪽, 서쪽, 북쪽에 있는 인접 셀들
  // 대응되는 번호의 정점 이어주기
  for (int t = 0; t < 4; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        int idx = timeWallCellId[t][i][j];
 
        for (int k = 0; k < 4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k];
 
          // 행 범위가 넘어갔을 경우 통과
          if (nx < 0 || nx >= M) continue;
 
          // 열 번호가 0보다 작아질 경우,
          // 시계방향순으로 하나 앞에 있는 단면도의 가장 오른쪽 열의 셀과 인접
          if (ny < 0) {
            graph[idx][k] = timeWallCellId[(t + 1) % 4][nx][M - 1];
          }
 
          // 행 번호가 M-1보다 커질 경우,
          // 반시계방향순으로 하나 앞에 있는 단면도의 가장 왼쪽 열의 셀과 인접
          else if (ny >= M) {
            graph[idx][k] = timeWallCellId[(t + 3) % 4][nx][0];
          }
 
          // 그 외의 경우 평면도의 경우처럼 이어줍니다
          else {
            graph[idx][k] = timeWallCellId[t][nx][ny];
          }
        }
      }
    }
  }
 
  // 위쪽 단면도에 속하는 셀들에 대응되는 번호의 정점 쌍에 대한 간선 추가
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      int idx = timeWallCellId[4][i][j];
 
      for (int k = 0; k < 4; k++) {
        int nx = i + dx[k];
        int ny = j + dy[k];
 
        if (nx < 0 || ny < 0 || nx >= M || ny >= M) continue;
 
        graph[idx][k] = timeWallCellId[4][nx][ny];
      }
    }
  }
 
  // 동
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][i][M - 1];
    int idy = timeWallCellId[0][0][M - 1 - i];
    graph[idx][0] = idy;
    graph[idy][3] = idx;
  }
 
  // 남
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][M - 1][i];
    int idy = timeWallCellId[1][0][i];
    graph[idx][1] = idy;
    graph[idy][3] = idx;
  }
 
  // 서
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][i][0];
    int idy = timeWallCellId[2][0][i];
    graph[idx][2] = idy;
    graph[idy][3] = idx;
  }
 
  // 북
  for (int i = 0; i < M; i++) {
    int idx = timeWallCellId[4][0][i];
    int idy = timeWallCellId[3][0][M - 1 - i];
    graph[idx][3] = idy;
    graph[idy][3] = idx;
  }
 
  int timewallStartx = -1;
  int timewallStarty = -1;
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 3) {
        timewallStartx = i;
        timewallStarty = j;
        break;
      }
    }
    if (timewallStartx != -1) break;
  }
 
  // 평면도와 인접하는 단면도 셀들에 대응되는 번호의 정점을 잇는 간선 추가
  // 동
  if (timewallStarty + M < N) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[0][M - 1][i];
      int idy =
          spaceMapCellId[timewallStartx + (M - 1) - i][timewallStarty + M];
      graph[idx][1] = idy;
      graph[idy][2] = idx;
    }
  }
 
  // 남
  if (timewallStartx + M < N) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[1][M - 1][i];
      int idy = spaceMapCellId[timewallStartx + M][timewallStarty + i];
      graph[idx][1] = idy;
      graph[idy][3] = idx;
    }
  }
 
  // 서
  if (timewallStarty > 0) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[2][M - 1][i];
      int idy = spaceMapCellId[timewallStartx + i][timewallStarty - 1];
      graph[idx][1] = idy;
      graph[idy][0] = idx;
    }
  }
 
  // 북
  if (timewallStartx > 0) {
    for (int i = 0; i < M; i++) {
      int idx = timeWallCellId[3][M - 1][i];
      int idy =
          spaceMapCellId[timewallStartx - 1][timewallStarty + (M - 1) - i];
      graph[idx][1] = idy;
      graph[idy][1] = idx;
    }
  }
 
  return;
}
 
void initializingGraph() {
  // 생성된 그래프의 정점의 개수는
  // N*N - M*M + 5*M*M = N*N + 4*M*M 개
  // -1로 배열의 값을 초기화
 
  fill(dist, dist + (N * N) + 4 * (M * M) + 1, -1);
 
  // 장애물인 경우 도달할 수 없으므로 미리 큰 값으로 세팅
  // 평면도에 있는 장애물의 경우
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 3) continue;
      if (spaceMap[i][j] == 1) {
        int idx = spaceMapCellId[i][j];
        dist[idx] = INF;
      }
    }
  }
 
  // 평면도에서 시간 이상 현상의 시작점도 도달 불가능하므로 장애물과 같이 처리
  for (int i = 1; i <= E; i++) {
    int x = events[i].xpos;
    int y = events[i].ypos;
    int idx = spaceMapCellId[x][y];
    dist[idx] = INF;
  }
 
  // 단면도 위에 있는 장애물의 경우 역시 똑같이 처리
  for (int t = 0; t < 5; t++) {
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < M; j++) {
        if (timeWall[t][i][j] == 1) {
          int idx = timeWallCellId[t][i][j];
          dist[idx] = INF;
        }
      }
    }
  }
}
 
void bfsAndCalculate() {
  queue<int> q;
 
  int cellStart = -1;
  int cellEnd = -1;
 
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if (timeWall[4][i][j] == 2) {
        cellStart = timeWallCellId[4][i][j];
        break;
      }
    }
  }
 
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (spaceMap[i][j] == 4) {
        cellEnd = spaceMapCellId[i][j];
        break;
      }
    }
  }
 
  q.push(cellStart);
  dist[cellStart] = 0;
 
  for (int runs = 1;; runs++) {
    // 이상현상이 있는 경우 영향을 받는 셀들 업데이트
    for (int i = 1; i <= E; i++) {
      if (!events[i].alive) continue;
      if (runs % events[i].cycle) continue;
 
      // 이상현상 시작점
      int nx = events[i].xpos, ny = events[i].ypos;
 
      // 이상현상의 방향에 따라 영향을 받는 셀의 좌표
      if (events[i].direction == 0) {
        ny += (runs / events[i].cycle);
      } else if (events[i].direction == 1) {
        nx += (runs / events[i].cycle);
      } else if (events[i].direction == 2) {
        ny -= (runs / events[i].cycle);
      } else {
        nx -= (runs / events[i].cycle);
      }
 
      if (nx < 0 || ny < 0 || nx >= N || ny >= N) {
        events[i].alive = 0;
        continue;
      }
 
      // 이상현상이 장애물이나 탈출구, 시간의 벽을 만난 경우, 확산하지 않습니다
      if (spaceMap[nx][ny]) {
        events[i].alive = 0;
        continue;
      }
 
      // 이상현상 적용
      int idx = spaceMapCellId[nx][ny];
      dist[idx] = INF;
    }
 
    vector<int> nextCells;
 
    // 이번턴에 도달 가능한 셀들 찾기
    while (!q.empty()) {
      int idx = q.front();
      q.pop();
 
      for (int i = 0; i < 4; i++) {
        int idy = graph[idx][i];
        if (idy == -1) continue;
        if (dist[idy] != -1) continue;
        dist[idy] = runs;
        nextCells.push_back(idy);
      }
    }
    int nextCellsSize = nextCells.size();
 
    if (!nextCellsSize) {
      break;
    }
 
    for (int i = 0; i < nextCellsSize; i++) {
      q.push(nextCells[i]);
    }
 
    if (dist[cellEnd] != -1) {
      break;
    }
  }
 
  cout << dist[cellEnd];
}