알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 미지의 공간 탈출 (삼성 SW 역량테스트 2024 하반기 오전 1번)
피로물든딸기
2024. 10. 17. 21:42
반응형
참고
https://www.codetree.ai/training-field/frequent-problems/problems/escape-unknown-space
문제에서 정의된 값을 다음과 같이 define 한다.
EAST ~ NORTH는 큐브의 각 옆면을 의미하고, TOP은 큐브의 위, BOTTOM은 미지의 공간이 된다.
#define EAST (0)
#define WEST (1)
#define SOUTH (2)
#define NORTH (3)
#define TOP (4)
#define BOTTOM (5)
#define EMPTY (0)
#define WALL (1)
#define TIME_MACHINE (2)
#define CUBE (3)
#define EXIT (4)
방향도 EAST ~ NORTH에 맞춰서 선언한다.
#define RIGHT (0)
#define LEFT (1)
#define DOWN (2)
#define UP (3)
EAST ~ BOTTOM까지 MAP은 3차원 배열에 저장한다.
BFS 탐색을 위한 visit 배열을 선언한다.
TIME_WALL은 시간 이상 현상이 만들어내는 벽을 의미한다.
int N, M, F;
int MAP[6][MAX][MAX];
int visit[6][MAX][MAX];
int TIME_WALL[6][MAX][MAX];
입구와 출구는 RC 구조체에 입력받는다.
struct RC
{
int r;
int c;
};
RC start, end;
BFS는 해당되는 평면 Plane (EAST ~ BOTTOM)과 좌표 (r, c)를 큐에 넣어서 시작한다.
struct PRC
{
int p; // plane
int r;
int c;
};
PRC queue[MAX * MAX * 6];
4차원 배열 next는 전처리를 이용하기 위해 선언한다.
예를 들어 next[TOP][1][i][UP]은 TOP 평면의 (1, i)에서 위(↑)로 갈 경우 변경되는 평면과 좌표 (r, c)가 된다.
PRC next[6][MAX][MAX][4];
시간 이상현상에 대한 정보는 다음 구조체에 정의한다.
struct TIME_INFO
{
int p;
int r;
int c;
int d;
int v;
};
TIME_INFO timeInfo[10 + 3];
동, 서, 남, 북 / 오른쪽, 왼쪽, 아래, 위에 해당하는 방향 배열은 다음과 같다.
// →, ←, ↓, ↑
int dr[] = { 0, 0, 1, -1 };
int dc[] = { 1, -1, 0, 0 };
input은 다음과 같다.
BOTTOM의 r, c가 EXIT인 경우 end에 좌표를 저장하고,
TOP의 r, c가 TIME_MACHINE인 경우 start에 좌표를 저장하였다.
void input()
{
scanf("%d %d %d", &N, &M, &F);
// init
for (int i = 0; i < 6; i++)
for (int r = 0; r < MAX; r++)
for (int c = 0; c < MAX; c++)
MAP[i][r][c] = visit[i][r][c] = TIME_WALL[i][r][c] = 0;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
scanf("%d", &MAP[BOTTOM][r][c]);
if (MAP[BOTTOM][r][c] == EXIT)
{
end.r = r;
end.c = c;
}
}
}
for (int i = 0; i < 5; i++)
{
for (int r = 1; r <= M; r++)
{
for (int c = 1; c <= M; c++)
{
scanf("%d", &MAP[i][r][c]);
if (MAP[TOP][r][c] == TIME_MACHINE)
{
start.r = r;
start.c = c;
}
}
}
}
for (int f = 0; f < F; f++)
{
int r, c, d, v;
scanf("%d %d %d %d", &r, &c, &d, &v);
timeInfo[f].p = BOTTOM;
timeInfo[f].r = r + 1;
timeInfo[f].c = c + 1;
timeInfo[f].d = d;
timeInfo[f].v = v;
}
}
시간 이상 현상은 모두 BOTTOM에서 시작한다.
그리고 (0, 0) 부터 시작하는 좌표를 (1, 1)부터 시작하도록 수정하였다.
for (int f = 0; f < F; f++)
{
int r, c, d, v;
scanf("%d %d %d %d", &r, &c, &d, &v);
timeInfo[f].p = BOTTOM;
timeInfo[f].r = r + 1;
timeInfo[f].c = c + 1;
timeInfo[f].d = d;
timeInfo[f].v = v;
}
디버깅 함수는 다음과 같다.
void printMap(int map[MAX][MAX], int size)
{
for (int r = 1; r <= size; r++)
{
for (int c = 1; c <= size; c++)
printf("%d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
void printMapAll(int map[6][MAX][MAX])
{
printf("BOTTOM\n");
printMap(map[BOTTOM], N);
printf("EAST\n");
printMap(map[EAST], M);
printf("WEST\n");
printMap(map[WEST], M);
printf("SOUTH\n");
printMap(map[SOUTH], M);
printf("NORTH\n");
printMap(map[NORTH], M);
printf("TOP\n");
printMap(map[TOP], M);
}전처리
문제에서 주어진 예시의 큐브를 전개도로 펼치면 다음과 같다.
BFS에서 각 평면의 경계를 넘어가는 경우 다른 평면으로 이동하기 때문에 전처리를 해두면 편하다.
예를 들어 TOP (1, i)에서 ↑ 가면 NORTH (1, M + 1 - i)가 된다.
코드로 구현하면 next 배열에 다음과 같이 구현할 수 있다.
for (int i = 1; i <= M; i++)
{
// TOP (1, i)에서 ↑ 가면 NORTH (1, M + 1 - i)
next[TOP][1][i][UP].p = NORTH;
next[TOP][1][i][UP].r = 1;
next[TOP][1][i][UP].c = M + 1 - i;
...
}
반대로 NORTH (1, i)에서 ↑ 가면 TOP (1, M + 1 - i)가 되므로 다음과 같이 전처리가 가능하다.
for (int i = 1; i <= M; i++)
{
// TOP (1, i)에서 ↑ 가면 NORTH (1, M + 1 - i)
...
// NORTH (1, i)에서 ↑ 가면 TOP (1, M + 1 - i)
next[NORTH][1][i][UP].p = TOP;
next[NORTH][1][i][UP].r = 1;
next[NORTH][1][i][UP].c = M + 1 - i;
}
그리고 동/서/남/북 평면에서 각각 왼쪽, 오른쪽으로 가는 경우도 전처리 할 수 있다.
예를 들어 SOUTH (i, M)에서 → 가면 EAST (i, 1)가 된다.
코드로 구현하면 다음과 같다.
// →
for (int i = 1; i <= M; i++)
{
// SOUTH (i, M)에서 → 가면 EAST (i, 1)
next[SOUTH][i][M][RIGHT].p = EAST;
next[SOUTH][i][M][RIGHT].r = i;
next[SOUTH][i][M][RIGHT].c = 1;
...
}
반대인 경우는 다음과 같다.
// ←
for (int i = 1; i <= M; i++)
{
// EAST (i, 1)에서 ← 가면 SOUTH (i, M)
next[EAST][i][1][LEFT].p = SOUTH;
next[EAST][i][1][LEFT].r = i;
next[EAST][i][1][LEFT].c = M;
...
}
이제 동/서/남/북에서 BOTTOM으로 이동하거나 BOTTOM에서 동/서/남/북으로 이동하는 경우를 처리해야 한다.
BOTTOM에서 WEST로 넘어가는 경우는 이중 for문에서 r을 고정하고 c를 증가시키면서
MAP[BOTTOM][r][c]가 3 (CUBE)인 경우 평면이 바뀐다.
c를 1부터 증가시켰을 때, BOTTOM의 r, c가 CUBE인 경우, WEST 평면이기 때문에
BOTTOM의 (r, c - 1)에서 RIGHT로 이동하면 WEST가 된다.
그리고 좌표는 (M, 1)이 되고 그 다음 좌표는 (M, 2)가 되므로 index를 이용해 좌표를 갱신한다.
반대로 WEST의 (M, 1)에서 DOWN으로 이동하면 BOTTOM이 되고, (r, c - 1)이 된다.
코드로 구현하면 다음과 같다.
// BOTTOM, WEST
index = 1;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// BOTTOM → WEST
next[BOTTOM][r][c - 1][RIGHT].p = WEST;
next[BOTTOM][r][c - 1][RIGHT].r = M;
next[BOTTOM][r][c - 1][RIGHT].c = index;
// BOTTOM ← WEST = (↓)
next[WEST][M][index][DOWN].p = BOTTOM;
next[WEST][M][index][DOWN].r = r;
next[WEST][M][index][DOWN].c = c - 1;
index++;
break;
}
}
}
단, 시간의 벽에서 미지의 공간으로 이어지는 출구가 하나라고 했기 때문에
BOTTOM에서 동/서/남/북으로 이동하는 경우는 없으므로, 아래 경우는 지워도 된다.
// BOTTOM → WEST
next[BOTTOM][r][c - 1][RIGHT].p = WEST;
next[BOTTOM][r][c - 1][RIGHT].r = M;
next[BOTTOM][r][c - 1][RIGHT].c = index;
전체 전처리 코드는 다음과 같다.
void preprocess()
{
for (int i = 1; i <= M; i++)
{
// TOP (1, i)에서 ↑ 가면 NORTH (1, M + 1 - i)
next[TOP][1][i][UP].p = NORTH;
next[TOP][1][i][UP].r = 1;
next[TOP][1][i][UP].c = M + 1 - i;
// NORTH (1, i)에서 ↑ 가면 TOP (1, M + 1 - i)
next[NORTH][1][i][UP].p = TOP;
next[NORTH][1][i][UP].r = 1;
next[NORTH][1][i][UP].c = M + 1 - i;
// ------------------------------------- //
// TOP (M, i)에서 ↓ 가면 SOUTH (1, i)
next[TOP][M][i][DOWN].p = SOUTH;
next[TOP][M][i][DOWN].r = 1;
next[TOP][M][i][DOWN].c = i;
// SOUTH (1, i)에서 ↑ 가면 TOP (M, i)
next[SOUTH][1][i][UP].p = TOP;
next[SOUTH][1][i][UP].r = M;
next[SOUTH][1][i][UP].c = i;
// ------------------------------------- //
// TOP (i, M)에서 → 가면 EAST (1, M + 1 - i)
next[TOP][i][M][RIGHT].p = EAST;
next[TOP][i][M][RIGHT].r = 1;
next[TOP][i][M][RIGHT].c = M + 1 - i;
// EAST (1, i)에서 ↑ 가면 TOP (M + 1 - i, M)
next[EAST][1][i][UP].p = TOP;
next[EAST][1][i][UP].r = M + 1 - i;
next[EAST][1][i][UP].c = M;
// ------------------------------------- //
// TOP (i, 1)에서 ← 가면 WEST (1, i)
next[TOP][i][1][LEFT].p = WEST;
next[TOP][i][1][LEFT].r = 1;
next[TOP][i][1][LEFT].c = i;
// WEST (1, i)에서 ↑ 가면 TOP (i, 1)
next[WEST][1][i][UP].p = TOP;
next[WEST][1][i][UP].r = i;
next[WEST][1][i][UP].c = 1;
}
// →
for (int i = 1; i <= M; i++)
{
// SOUTH (i, M)에서 → 가면 EAST (i, 1)
next[SOUTH][i][M][RIGHT].p = EAST;
next[SOUTH][i][M][RIGHT].r = i;
next[SOUTH][i][M][RIGHT].c = 1;
// EAST (i, M)에서 → 가면 NORTH (i, 1)
next[EAST][i][M][RIGHT].p = NORTH;
next[EAST][i][M][RIGHT].r = i;
next[EAST][i][M][RIGHT].c = 1;
// NORTH (i, M)에서 → 가면 WEST (i, 1)
next[NORTH][i][M][RIGHT].p = WEST;
next[NORTH][i][M][RIGHT].r = i;
next[NORTH][i][M][RIGHT].c = 1;
// WEST (i, M)에서 → 가면 SOUTH (i, 1)
next[WEST][i][M][RIGHT].p = SOUTH;
next[WEST][i][M][RIGHT].r = i;
next[WEST][i][M][RIGHT].c = 1;
}
// ←
for (int i = 1; i <= M; i++)
{
// SOUTH (i, 1)에서 ← 가면 WEST (i, M)
next[SOUTH][i][1][LEFT].p = WEST;
next[SOUTH][i][1][LEFT].r = i;
next[SOUTH][i][1][LEFT].c = M;
// WEST (i, 1)에서 ← 가면 NORTH (i, M)
next[WEST][i][1][LEFT].p = NORTH;
next[WEST][i][1][LEFT].r = i;
next[WEST][i][1][LEFT].c = M;
// NORTH (i, 1)에서 ← 가면 EAST (i, M)
next[NORTH][i][1][LEFT].p = EAST;
next[NORTH][i][1][LEFT].r = i;
next[NORTH][i][1][LEFT].c = M;
// EAST (i, 1)에서 ← 가면 SOUTH (i, M)
next[EAST][i][1][LEFT].p = SOUTH;
next[EAST][i][1][LEFT].r = i;
next[EAST][i][1][LEFT].c = M;
}
int index;
// BOTTOM, WEST
index = 1;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// BOTTOM → WEST
next[BOTTOM][r][c - 1][RIGHT].p = WEST;
next[BOTTOM][r][c - 1][RIGHT].r = M;
next[BOTTOM][r][c - 1][RIGHT].c = index;
// BOTTOM ← WEST = (↓)
next[WEST][M][index][DOWN].p = BOTTOM;
next[WEST][M][index][DOWN].r = r;
next[WEST][M][index][DOWN].c = c - 1;
index++;
break;
}
}
}
// BOTTOM, EAST
index = M;
for (int r = 1; r <= N; r++)
{
for (int c = N; c >= 1; c--)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// EAST ← BOTTOM
next[BOTTOM][r][c + 1][LEFT].p = EAST;
next[BOTTOM][r][c + 1][LEFT].r = M;
next[BOTTOM][r][c + 1][LEFT].c = index;
// EAST → BOTTOM = (↓)
next[EAST][M][index][DOWN].p = BOTTOM;
next[EAST][M][index][DOWN].r = r;
next[EAST][M][index][DOWN].c = c + 1;
index--;
break;
}
}
}
// BOTTOM, NORTH
index = M;
for (int c = 1; c <= N; c++)
{
for (int r = 1; r <= N; r++)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// BOTTOM
// ↓
// NORTH = ↓
next[BOTTOM][r - 1][c][DOWN].p = NORTH;
next[BOTTOM][r - 1][c][DOWN].r = M;
next[BOTTOM][r - 1][c][DOWN].c = index;
// BOTTOM
// ↑
// NORTH = ↓
next[NORTH][M][index][DOWN].p = BOTTOM;
next[NORTH][M][index][DOWN].r = r - 1;
next[NORTH][M][index][DOWN].c = c;
index--;
break;
}
}
}
// BOTTOM, SOUTH
index = 1;
for (int c = 1; c <= N; c++)
{
for (int r = N; r >= 1; r--)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// SOUTH
// ↑
// BOTTOM = ↑
next[BOTTOM][r + 1][c][UP].p = SOUTH;
next[BOTTOM][r + 1][c][UP].r = M;
next[BOTTOM][r + 1][c][UP].c = index;
// SOUTH
// ↓
// BOTTOM = ↓
next[SOUTH][M][index][DOWN].p = BOTTOM;
next[SOUTH][M][index][DOWN].r = r + 1;
next[SOUTH][M][index][DOWN].c = c;
index++;
break;
}
}
}
}시간 이상 현상
모든 시간 현상에 대해 움직일 수 있을 때 까지, TIME_WALL에 시간을 마킹한다.
1부터 마킹하고 다음 칸은 (1 + v)를 마킹해두면 된다.
마킹을 잘 하면, TIME_WALL이 0이 아니고,
visit(최단거리 기록)가 TIME_WALL보다 큰 경우는 시간 현상의 벽이 있다고 판단할 수 있다.
이 경우는 이동하지 못하는 칸이 된다.
if (TIME_WALL[np][nr][nc] != 0
&& visit[out.p][out.r][out.c] + 1 >= TIME_WALL[np][nr][nc]) continue;
BOTTOM에서 다음 좌표 (nr, nc)가 CUBE인 경우 전처리 해둔, next 배열로 평면과 좌표를 바꾼다.
int np, nr, nc;
np = p;
nr = r + dr[d];
nc = c + dc[d];
if (p == BOTTOM && MAP[BOTTOM][nr][nc] == CUBE)
{
np = next[BOTTOM][r][c][d].p;
nr = next[BOTTOM][r][c][d].r;
nc = next[BOTTOM][r][c][d].c;
}
그 외 좌표는 다음과 같이 경계를 벗어날 때, 좌표를 바꿀 수 있다.
else if ((p != BOTTOM) && (nr < 1 || nc < 1 || nr > M || nc > M))
{
np = next[p][r][c][d].p;
nr = next[p][r][c][d].r;
nc = next[p][r][c][d].c;
}
BOTTOM에서 경계를 벗어나거나, 벽이 있거나, 탈출구인 경우는 시간 이상 현상 마킹을 종료한다.
if ((np == BOTTOM) && (nr < 1 || nc < 1 || nr > N || nc > N)) break;
if (MAP[np][nr][nc] == WALL) break;
if (nr == end.r && nc == end.c) break;
전체 코드는 다음과 같다.
void makeTime()
{
for (int f = 0; f < F; f++)
{
int p, r, c, d, v;
p = timeInfo[f].p;
r = timeInfo[f].r;
c = timeInfo[f].c;
d = timeInfo[f].d;
v = timeInfo[f].v;
TIME_WALL[p][r][c] = 1;
while (1)
{
int np, nr, nc;
np = p;
nr = r + dr[d];
nc = c + dc[d];
if (p == BOTTOM && MAP[BOTTOM][nr][nc] == CUBE)
{
np = next[BOTTOM][r][c][d].p;
nr = next[BOTTOM][r][c][d].r;
nc = next[BOTTOM][r][c][d].c;
}
else if ((p != BOTTOM) && (nr < 1 || nc < 1 || nr > M || nc > M))
{
np = next[p][r][c][d].p;
nr = next[p][r][c][d].r;
nc = next[p][r][c][d].c;
}
if ((np == BOTTOM) && (nr < 1 || nc < 1 || nr > N || nc > N)) break;
if (MAP[np][nr][nc] == WALL) break;
if (nr == end.r && nc == end.c) break;
TIME_WALL[np][nr][nc] = TIME_WALL[p][r][c] + v;
p = np;
r = nr;
c = nc;
}
}
}BFS
벽 부수고 이동하기를 참고하여 visit에 최단거리를 마킹한다.
TOP의 start (r, c)에서 탐색을 시작하고, BOTTOM의 end (r, c)를 찾으면 종료한다.
경계를 벗어나는 경우 전처리 해둔 next 배열로 다음 좌표를 찾으면 된다.
int BFS(int r, int c)
{
int rp, wp;
rp = wp = 0;
visit[TOP][r][c] = 1;
queue[wp].p = TOP;
queue[wp].r = r;
queue[wp++].c = c;
while (rp < wp)
{
PRC out = queue[rp++];
if (out.p == BOTTOM && out.r == end.r && out.c == end.c)
return visit[BOTTOM][out.r][out.c] - 1;
for (int i = 0; i < 4; i++)
{
int np, nr, nc;
np = out.p;
nr = out.r + dr[i];
nc = out.c + dc[i];
if (out.p == BOTTOM && MAP[BOTTOM][nr][nc] == CUBE)
{
np = next[BOTTOM][out.r][out.c][i].p;
nr = next[BOTTOM][out.r][out.c][i].r;
nc = next[BOTTOM][out.r][out.c][i].c;
}
else if ((out.p != BOTTOM) && (nr < 1 || nc < 1 || nr > M || nc > M))
{
np = next[out.p][out.r][out.c][i].p;
nr = next[out.p][out.r][out.c][i].r;
nc = next[out.p][out.r][out.c][i].c;
}
if ((np == BOTTOM) && (nr < 1 || nc < 1 || nr > N || nc > N)) continue;
if (MAP[np][nr][nc] == WALL || visit[np][nr][nc] != 0) continue;
if (TIME_WALL[np][nr][nc] != 0
&& visit[out.p][out.r][out.c] + 1 >= TIME_WALL[np][nr][nc]) continue;
queue[wp].p = np;
queue[wp].r = nr;
queue[wp++].c = nc;
visit[np][nr][nc] = visit[out.p][out.r][out.c] + 1;
}
}
return -1;
}전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (20 + 5)
#define EAST (0)
#define WEST (1)
#define SOUTH (2)
#define NORTH (3)
#define TOP (4)
#define BOTTOM (5)
#define EMPTY (0)
#define WALL (1)
#define TIME_MACHINE (2)
#define CUBE (3)
#define EXIT (4)
#define RIGHT (0)
#define LEFT (1)
#define DOWN (2)
#define UP (3)
int T;
int N, M, F;
int MAP[6][MAX][MAX];
int visit[6][MAX][MAX];
int TIME_WALL[6][MAX][MAX];
struct RC
{
int r;
int c;
};
RC start, end;
struct PRC
{
int p; // plane
int r;
int c;
};
PRC queue[MAX * MAX * 6];
PRC next[6][MAX][MAX][4];
struct TIME_INFO
{
int p;
int r;
int c;
int d;
int v;
};
TIME_INFO timeInfo[10 + 3];
// →, ←, ↓, ↑
int dr[] = { 0, 0, 1, -1 };
int dc[] = { 1, -1, 0, 0 };
void input()
{
scanf("%d %d %d", &N, &M, &F);
// init
for (int i = 0; i < 6; i++)
for (int r = 0; r < MAX; r++)
for (int c = 0; c < MAX; c++)
MAP[i][r][c] = visit[i][r][c] = TIME_WALL[i][r][c] = 0;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
scanf("%d", &MAP[BOTTOM][r][c]);
if (MAP[BOTTOM][r][c] == EXIT)
{
end.r = r;
end.c = c;
}
}
}
for (int i = 0; i < 5; i++)
{
for (int r = 1; r <= M; r++)
{
for (int c = 1; c <= M; c++)
{
scanf("%d", &MAP[i][r][c]);
if (MAP[TOP][r][c] == TIME_MACHINE)
{
start.r = r;
start.c = c;
}
}
}
}
for (int f = 0; f < F; f++)
{
int r, c, d, v;
scanf("%d %d %d %d", &r, &c, &d, &v);
timeInfo[f].p = BOTTOM;
timeInfo[f].r = r + 1;
timeInfo[f].c = c + 1;
timeInfo[f].d = d;
timeInfo[f].v = v;
}
}
void printMap(int map[MAX][MAX], int size)
{
for (int r = 1; r <= size; r++)
{
for (int c = 1; c <= size; c++)
printf("%d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
void printMapAll(int map[6][MAX][MAX])
{
printf("BOTTOM\n");
printMap(map[BOTTOM], N);
printf("EAST\n");
printMap(map[EAST], M);
printf("WEST\n");
printMap(map[WEST], M);
printf("SOUTH\n");
printMap(map[SOUTH], M);
printf("NORTH\n");
printMap(map[NORTH], M);
printf("TOP\n");
printMap(map[TOP], M);
}
void preprocess()
{
for (int i = 1; i <= M; i++)
{
// TOP (1, i)에서 ↑ 가면 NORTH (1, M + 1 - i)
next[TOP][1][i][UP].p = NORTH;
next[TOP][1][i][UP].r = 1;
next[TOP][1][i][UP].c = M + 1 - i;
// NORTH (1, i)에서 ↑ 가면 TOP (1, M + 1 - i)
next[NORTH][1][i][UP].p = TOP;
next[NORTH][1][i][UP].r = 1;
next[NORTH][1][i][UP].c = M + 1 - i;
// ------------------------------------- //
// TOP (M, i)에서 ↓ 가면 SOUTH (1, i)
next[TOP][M][i][DOWN].p = SOUTH;
next[TOP][M][i][DOWN].r = 1;
next[TOP][M][i][DOWN].c = i;
// SOUTH (1, i)에서 ↑ 가면 TOP (M, i)
next[SOUTH][1][i][UP].p = TOP;
next[SOUTH][1][i][UP].r = M;
next[SOUTH][1][i][UP].c = i;
// ------------------------------------- //
// TOP (i, M)에서 → 가면 EAST (1, M + 1 - i)
next[TOP][i][M][RIGHT].p = EAST;
next[TOP][i][M][RIGHT].r = 1;
next[TOP][i][M][RIGHT].c = M + 1 - i;
// EAST (1, i)에서 ↑ 가면 TOP (M + 1 - i, M)
next[EAST][1][i][UP].p = TOP;
next[EAST][1][i][UP].r = M + 1 - i;
next[EAST][1][i][UP].c = M;
// ------------------------------------- //
// TOP (i, 1)에서 ← 가면 WEST (1, i)
next[TOP][i][1][LEFT].p = WEST;
next[TOP][i][1][LEFT].r = 1;
next[TOP][i][1][LEFT].c = i;
// WEST (1, i)에서 ↑ 가면 TOP (i, 1)
next[WEST][1][i][UP].p = TOP;
next[WEST][1][i][UP].r = i;
next[WEST][1][i][UP].c = 1;
}
// →
for (int i = 1; i <= M; i++)
{
// SOUTH (i, M)에서 → 가면 EAST (i, 1)
next[SOUTH][i][M][RIGHT].p = EAST;
next[SOUTH][i][M][RIGHT].r = i;
next[SOUTH][i][M][RIGHT].c = 1;
// EAST (i, M)에서 → 가면 NORTH (i, 1)
next[EAST][i][M][RIGHT].p = NORTH;
next[EAST][i][M][RIGHT].r = i;
next[EAST][i][M][RIGHT].c = 1;
// NORTH (i, M)에서 → 가면 WEST (i, 1)
next[NORTH][i][M][RIGHT].p = WEST;
next[NORTH][i][M][RIGHT].r = i;
next[NORTH][i][M][RIGHT].c = 1;
// WEST (i, M)에서 → 가면 SOUTH (i, 1)
next[WEST][i][M][RIGHT].p = SOUTH;
next[WEST][i][M][RIGHT].r = i;
next[WEST][i][M][RIGHT].c = 1;
}
// ←
for (int i = 1; i <= M; i++)
{
// SOUTH (i, 1)에서 ← 가면 WEST (i, M)
next[SOUTH][i][1][LEFT].p = WEST;
next[SOUTH][i][1][LEFT].r = i;
next[SOUTH][i][1][LEFT].c = M;
// WEST (i, 1)에서 ← 가면 NORTH (i, M)
next[WEST][i][1][LEFT].p = NORTH;
next[WEST][i][1][LEFT].r = i;
next[WEST][i][1][LEFT].c = M;
// NORTH (i, 1)에서 ← 가면 EAST (i, M)
next[NORTH][i][1][LEFT].p = EAST;
next[NORTH][i][1][LEFT].r = i;
next[NORTH][i][1][LEFT].c = M;
// EAST (i, 1)에서 ← 가면 SOUTH (i, M)
next[EAST][i][1][LEFT].p = SOUTH;
next[EAST][i][1][LEFT].r = i;
next[EAST][i][1][LEFT].c = M;
}
int index;
// BOTTOM, WEST
index = 1;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// BOTTOM → WEST
next[BOTTOM][r][c - 1][RIGHT].p = WEST;
next[BOTTOM][r][c - 1][RIGHT].r = M;
next[BOTTOM][r][c - 1][RIGHT].c = index;
// BOTTOM ← WEST = (↓)
next[WEST][M][index][DOWN].p = BOTTOM;
next[WEST][M][index][DOWN].r = r;
next[WEST][M][index][DOWN].c = c - 1;
index++;
break;
}
}
}
// BOTTOM, EAST
index = M;
for (int r = 1; r <= N; r++)
{
for (int c = N; c >= 1; c--)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// EAST ← BOTTOM
next[BOTTOM][r][c + 1][LEFT].p = EAST;
next[BOTTOM][r][c + 1][LEFT].r = M;
next[BOTTOM][r][c + 1][LEFT].c = index;
// EAST → BOTTOM = (↓)
next[EAST][M][index][DOWN].p = BOTTOM;
next[EAST][M][index][DOWN].r = r;
next[EAST][M][index][DOWN].c = c + 1;
index--;
break;
}
}
}
// BOTTOM, NORTH
index = M;
for (int c = 1; c <= N; c++)
{
for (int r = 1; r <= N; r++)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// BOTTOM
// ↓
// NORTH = ↓
next[BOTTOM][r - 1][c][DOWN].p = NORTH;
next[BOTTOM][r - 1][c][DOWN].r = M;
next[BOTTOM][r - 1][c][DOWN].c = index;
// BOTTOM
// ↑
// NORTH = ↓
next[NORTH][M][index][DOWN].p = BOTTOM;
next[NORTH][M][index][DOWN].r = r - 1;
next[NORTH][M][index][DOWN].c = c;
index--;
break;
}
}
}
// BOTTOM, SOUTH
index = 1;
for (int c = 1; c <= N; c++)
{
for (int r = N; r >= 1; r--)
{
if (MAP[BOTTOM][r][c] == CUBE)
{
// SOUTH
// ↑
// BOTTOM = ↑
next[BOTTOM][r + 1][c][UP].p = SOUTH;
next[BOTTOM][r + 1][c][UP].r = M;
next[BOTTOM][r + 1][c][UP].c = index;
// SOUTH
// ↓
// BOTTOM = ↓
next[SOUTH][M][index][DOWN].p = BOTTOM;
next[SOUTH][M][index][DOWN].r = r + 1;
next[SOUTH][M][index][DOWN].c = c;
index++;
break;
}
}
}
}
void makeTime()
{
for (int f = 0; f < F; f++)
{
int p, r, c, d, v;
p = timeInfo[f].p;
r = timeInfo[f].r;
c = timeInfo[f].c;
d = timeInfo[f].d;
v = timeInfo[f].v;
TIME_WALL[p][r][c] = 1;
while (1)
{
int np, nr, nc;
np = p;
nr = r + dr[d];
nc = c + dc[d];
if (p == BOTTOM && MAP[BOTTOM][nr][nc] == CUBE)
{
np = next[BOTTOM][r][c][d].p;
nr = next[BOTTOM][r][c][d].r;
nc = next[BOTTOM][r][c][d].c;
}
else if ((p != BOTTOM) && (nr < 1 || nc < 1 || nr > M || nc > M))
{
np = next[p][r][c][d].p;
nr = next[p][r][c][d].r;
nc = next[p][r][c][d].c;
}
if ((np == BOTTOM) && (nr < 1 || nc < 1 || nr > N || nc > N)) break;
if (MAP[np][nr][nc] == WALL) break;
if (nr == end.r && nc == end.c) break;
TIME_WALL[np][nr][nc] = TIME_WALL[p][r][c] + v;
p = np;
r = nr;
c = nc;
}
}
}
int BFS(int r, int c)
{
int rp, wp;
rp = wp = 0;
visit[TOP][r][c] = 1;
queue[wp].p = TOP;
queue[wp].r = r;
queue[wp++].c = c;
while (rp < wp)
{
PRC out = queue[rp++];
if (out.p == BOTTOM && out.r == end.r && out.c == end.c)
return visit[BOTTOM][out.r][out.c] - 1;
for (int i = 0; i < 4; i++)
{
int np, nr, nc;
np = out.p;
nr = out.r + dr[i];
nc = out.c + dc[i];
if (out.p == BOTTOM && MAP[BOTTOM][nr][nc] == CUBE)
{
np = next[BOTTOM][out.r][out.c][i].p;
nr = next[BOTTOM][out.r][out.c][i].r;
nc = next[BOTTOM][out.r][out.c][i].c;
}
else if ((out.p != BOTTOM) && (nr < 1 || nc < 1 || nr > M || nc > M))
{
np = next[out.p][out.r][out.c][i].p;
nr = next[out.p][out.r][out.c][i].r;
nc = next[out.p][out.r][out.c][i].c;
}
if ((np == BOTTOM) && (nr < 1 || nc < 1 || nr > N || nc > N)) continue;
if (MAP[np][nr][nc] == WALL || visit[np][nr][nc] != 0) continue;
if (TIME_WALL[np][nr][nc] != 0
&& visit[out.p][out.r][out.c] + 1 >= TIME_WALL[np][nr][nc]) continue;
queue[wp].p = np;
queue[wp].r = nr;
queue[wp++].c = nc;
visit[np][nr][nc] = visit[out.p][out.r][out.c] + 1;
}
}
return -1;
}
int main()
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
preprocess();
makeTime();
//printf("TIME\n"); printMapAll(TIME);
//printf("MAP\n"); printMapAll(MAP);
printf("%d\n", BFS(start.r, start.c));
//printf("visit\n"); printMapAll(visit);
}
return 0;
}반응형