알고리즘/[ADV] 삼성 SW 역량 테스트 A형
[코드트리] 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번)
피로물든딸기
2024. 7. 31. 01:24
반응형
참고
- N x N 2차원 배열 뒤집기, 회전하기 (Rotate, Flip 2D Array)
https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner
좌표를 관리하는 구조체를 다음과 같이 선언한다.
기본적으로 2차원 배열의 (r, c)를 위해 사용하지만,
미로를 회전할 때, 영역의 크기를 size로, player의 탈출 여부를 escape로 관리한다.
typedef struct st1
{
int r;
int c;
int size; // 회전을 위한 크기
int escape; // Player 탈출 확인
}RC;
RC PLAYER[10 + 5];
RC EXIT;
상, 하, 좌, 우 우선순위로 움직이기 위해 배열을 선언한다.
#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)
// 상, 하, 좌, 우
int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
배열을 회전하기 위한 함수는 다음과 같다.
void copyMap(int src[MAX][MAX], int dest[MAX][MAX])
{
for (int i = 0; i < MAX; i++)
for (int k = 0; k < MAX; k++)
src[i][k] = dest[i][k];
}
void rotate(int map[MAX][MAX], int sr, int sc, int size)
{
int temp[MAX][MAX] = { 0 };
copyMap(temp, map);
for (int r = 0; r < size; r++)
for (int c = 0; c < size; c++)
map[r + sr][c + sc] = temp[size - 1 - c + sr][r + sc];
}
input은 다음과 같다.
MAP에는 벽만 관리하고, 참가자와 출구는 따로 관리한다.
필요한 경우에 MAP을 임시로 복사하고, 복사된 MAP에 참가자와 출구를 표시한다.
void input()
{
scanf("%d %d %d", &N, &M, &K);
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
for (int m = 0; m < M; m++)
{
scanf("%d %d", &PLAYER[m].r, &PLAYER[m].c);
PLAYER[m].escape = 0;
}
scanf("%d %d", &EXIT.r, &EXIT.c);
}
main은 다음과 같다.
1) move()에서 step 횟수를 구한 후, sum에서 누적한다.
2) allExitCheck()에서 모든 사람이 탈출했는지 체크한다. (true면 종료)
3) 미로를 회전한다.
int main(void)
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
int sum = 0;
for (int k = 0; k < K; k++)
{
int step = move();
sum += step;
if (allExitCheck() == true) break;
rotateMaze();
}
printf("%d\n", sum);
printf("%d %d\n", EXIT.r, EXIT.c);
}
return 0;
}
모든 사람이 탈출했는지 여부는 다음과 같이 간단히 확인할 수 있다.
int allExitCheck()
{
for (int p = 0; p < M; p++)
if (PLAYER[p].escape == 0) return 0;
return 1;
}플레이어 이동
move는 다음과 같다.
탈출하지 않은 모든 Player에 대해
1) 네 방향으로 움직일 경우의 좌표를 미리 구한다.
2) EXIT 좌표와 비교하여 상하 / 좌우로 움직일 수 있는지 먼저 확인한다. (checkRow, checkCol)
3) 상하 / 좌우 우선순위로 갈 수 있는 방향을 direction 변수에 저장한다. (with 벽 체크)
4) direction에 값이 있는 경우 Player의 좌표를 변경하고 step을 1 증가시킨다.
int move()
{
int step;
RC next;
step = 0;
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
// 4방향 좌표 할당
int nextR[4] = { 0 };
int nextC[4] = { 0 };
for (int i = 0; i < 4; i++)
{
nextR[i] = PLAYER[p].r + dr[i];
nextC[i] = PLAYER[p].c + dc[i];
}
int direction = -1;
// 상하로 움직이기
int upDown = checkRow(PLAYER[p]);
int leftRight = checkCol(PLAYER[p]);
// EXIT 방향으로 이동하므로 좌표를 벗어나지 않음.
if (upDown > 0 && MAP[nextR[UP]][nextC[UP]] == 0) direction = UP;
else if (upDown < 0 && MAP[nextR[DOWN]][nextC[DOWN]] == 0) direction = DOWN;
else if (leftRight > 0 && MAP[nextR[LEFT]][nextC[LEFT]] == 0) direction = LEFT;
else if (leftRight < 0 && MAP[nextR[RIGHT]][nextC[RIGHT]] == 0) direction = RIGHT;
if (direction == -1) continue;
PLAYER[p].r = PLAYER[p].r + dr[direction];
PLAYER[p].c = PLAYER[p].c + dc[direction];
if (PLAYER[p].r == EXIT.r && PLAYER[p].c == EXIT.c) PLAYER[p].escape = ESCAPE;
step++;
}
return step;
}
상하 / 좌우로 갈 수 있는지 판단하는 함수는 다음과 같다.
int checkRow(RC player)
{
int er = EXIT.r;
int pr = player.r;
// er > pr -> exit는 아래에
// er = pr -> 같은 행, 상하로 움직일 수 없음.
// er < pr -> exit는 위에
return er - pr;
}
int checkCol(RC player)
{
int ec = EXIT.c;
int pc = player.c;
// pc > ec -> exit는 왼쪽에
// ec = pc -> 같은 열, 좌우로 움직일 수 없음.
// pc < ec -> exit는 오른쪽에
return pc - ec;
}미로 회전
rotateMaze는 다음과 같다.
1) getRotateInfo에서 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형을 찾는다.
이때 return 되는 값 = rotateInfo에서 정사각형의 오른쪽 위 좌표와, size를 알 수 있다.
2) 해당되는 영역을 90도 회전한다.
3) EXIT 좌표를 90도 회전한다.
4) 해당되는 영역에 포함된 Player를 90도 회전한다.
5) 해당되는 영역에 포함된 벽의 내구도를 1씩 깎는다.
void rotateMaze()
{
RC rotateInfo = getRotateInfo();
rotate(MAP, rotateInfo.r, rotateInfo.c, rotateInfo.size);
EXIT = rotateRC(EXIT, rotateInfo);
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
if (isBoundary(PLAYER[p], rotateInfo) == 0) continue;
PLAYER[p] = rotateRC(PLAYER[p], rotateInfo);
}
wallDown(rotateInfo);
}
rotateInfo는 다음과 같이 구할 수 있다.
가장 작은 size = 2 부터, 행이 작고, 열이 작은 순서대로 정사각형 영역을 만든다.
그리고 MAP을 tmpMAP에 복사하고 tmpMAP에 Player와 EXIT 좌표를 추가한다.
이때, EXIT = -1 (EXIT_CHECK)로 표시하고, Player는 10보다 큰 값 (+ MARK = 10)으로 표기하여 벽과 구분하였다.
(탈출에 성공한 Player는 표시하지 않는다.)
그리고 rotateCheck에서 tmpMAP과 주어진 영역에 EXIT와 Player의 좌표가 있는지 확인한다.
RC getRotateInfo()
{
RC ret = { 0 };
for (int size = 2; size <= N; size++)
{
for (int r = 1; r <= N - size + 1; r++)
{
for (int c = 1; c <= N - size + 1; c++)
{
int tmpMAP[MAX][MAX] = { 0 };
copyMap(tmpMAP, MAP);
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
tmpMAP[PLAYER[p].r][PLAYER[p].c] = p + MARK;
}
tmpMAP[EXIT.r][EXIT.c] = EXIT_CHECK;
if (rotateCheck(tmpMAP, r, c, size) != 0)
{
ret.r = r;
ret.c = c;
ret.size = size;
return ret;
}
}
}
}
}
rotateCheck는 다음과 같다.
참고로 Player가 같은 좌표에 있더라도 한 명 이상이기만 하면 회전이 가능하다.
따라서 getRotateInfo에서 tmpMAP[PLAYER[p].r][PLAYER[p].c] = p + MARK; 로 충분하다.
int rotateCheck(int map[MAX][MAX], int sr, int sc, int size)
{
int exitCheck;
int playerCheck;
exitCheck = playerCheck = 0;
for (int r = sr; r < sr + size; r++)
{
for (int c = sc; c < sc + size; c++)
{
if (map[r][c] >= MARK) playerCheck++;
else if (map[r][c] == EXIT_CHECK) exitCheck = 1;
}
}
return exitCheck && playerCheck;
}
MAP에는 출구와 참가자가 없으므로, 따로 좌표를 구해야 한다.
하나의 좌표에 여러 참가자가 있을 수 있기 때문에 좌표를 구분하였다.
rotateRC 함수에서 좌표 rc와 rotateInfo를 이용해 좌표를 변경한다.
2차원 빈 배열에서 (출구 또는 참가자의) 좌표를 1로 표시하고, rotate를 한 후, 다시 1의 좌표를 찾으면 된다.
RC rotateRC(RC rc, RC rotateInfo)
{
RC ret = { 0 };
int tmpMAP[MAX][MAX] = { 0 };
tmpMAP[rc.r][rc.c] = 1;
rotate(tmpMAP, rotateInfo.r, rotateInfo.c, rotateInfo.size);
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (tmpMAP[r][c] == 1)
{
ret.r = r;
ret.c = c;
return ret;
}
}
}
ret.r = ret.c = -1; // error
return ret;
}
Player의 경우, 탈출하지 않고 영역에 있는 경우만 rotate한 좌표를 구한다.
void rotateMaze()
{
...
EXIT = rotateRC(EXIT, rotateInfo);
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
if (isBoundary(PLAYER[p], rotateInfo) == 0) continue;
PLAYER[p] = rotateRC(PLAYER[p], rotateInfo);
}
}
영역에 있는지는 다음과 같이 확인할 수 있다.
int isBoundary(RC rc, RC rotateInfo)
{
int sr = rotateInfo.r;
int er = rotateInfo.r + rotateInfo.size;
int sc = rotateInfo.c;
int ec = rotateInfo.c + rotateInfo.size;
return (sr <= rc.r && rc.r < er && sc <= rc.c && rc.c < ec);
}
마지막으로 해당되는 영역의 벽의 내구도를 감소한다.
void wallDown(RC rotateInfo)
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c] == 0) continue;
RC rc = { 0 };
rc.r = r;
rc.c = c;
if (isBoundary(rc, rotateInfo) == 0) continue;
MAP[r][c]--;
}
}
}전체 코드는 다음과 같다.
#include <stdio.h>
#define MAX (10 + 5)
#define MARK (10)
#define EXIT_CHECK (-1)
#define ESCAPE (10)
int T;
int N, M, K;
int MAP[MAX][MAX];
typedef struct st1
{
int r;
int c;
int size; // 회전을 위한 크기
int escape; // Player 탈출 확인
}RC;
RC PLAYER[10 + 5];
RC EXIT;
#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)
// 상, 하, 좌, 우
int dr[] = { 1, -1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
void input()
{
scanf("%d %d %d", &N, &M, &K);
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
scanf("%d", &MAP[r][c]);
for (int m = 0; m < M; m++)
{
scanf("%d %d", &PLAYER[m].r, &PLAYER[m].c);
PLAYER[m].escape = 0;
}
scanf("%d %d", &EXIT.r, &EXIT.c);
}
void printMap()
{
int temp[MAX][MAX];
for (int r = 1; r <= N; r++)
for (int c = 1; c <= N; c++)
temp[r][c] = MAP[r][c];
for (int p = 0; p < M; p++)
{
printf("%d : %d, %d (esc : %d)\n", p, PLAYER[p].r, PLAYER[p].c, PLAYER[p].escape);
if(PLAYER[p].escape == 0) temp[PLAYER[p].r][PLAYER[p].c] = p + MARK;
}
putchar('\n');
temp[EXIT.r][EXIT.c] = EXIT_CHECK;
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%2d ", temp[r][c]);
putchar('\n');
}
printf("============================\n");
}
void printMap(int map[MAX][MAX])
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
printf("%2d ", map[r][c]);
putchar('\n');
}
putchar('\n');
}
void copyMap(int src[MAX][MAX], int dest[MAX][MAX])
{
for (int i = 0; i < MAX; i++)
for (int k = 0; k < MAX; k++)
src[i][k] = dest[i][k];
}
void rotate(int map[MAX][MAX], int sr, int sc, int size)
{
int temp[MAX][MAX] = { 0 };
copyMap(temp, map);
for (int r = 0; r < size; r++)
for (int c = 0; c < size; c++)
map[r + sr][c + sc] = temp[size - 1 - c + sr][r + sc];
}
int checkRow(RC player)
{
int er = EXIT.r;
int pr = player.r;
// er > pr -> exit는 아래에
// er = pr -> 같은 행, 상하로 움직일 수 없음.
// er < pr -> exit는 위에
return er - pr;
}
int checkCol(RC player)
{
int ec = EXIT.c;
int pc = player.c;
// pc > ec -> exit는 왼쪽에
// ec = pc -> 같은 열, 좌우로 움직일 수 없음.
// pc < ec -> exit는 오른쪽에
return pc - ec;
}
int move()
{
int step;
RC next;
step = 0;
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
// 4방향 좌표 할당
int nextR[4] = { 0 };
int nextC[4] = { 0 };
for (int i = 0; i < 4; i++)
{
nextR[i] = PLAYER[p].r + dr[i];
nextC[i] = PLAYER[p].c + dc[i];
}
int direction = -1;
// 상하로 움직이기
int upDown = checkRow(PLAYER[p]);
int leftRight = checkCol(PLAYER[p]);
// EXIT 방향으로 이동하므로 좌표를 벗어나지 않음.
if (upDown > 0 && MAP[nextR[UP]][nextC[UP]] == 0) direction = UP;
else if (upDown < 0 && MAP[nextR[DOWN]][nextC[DOWN]] == 0) direction = DOWN;
else if (leftRight > 0 && MAP[nextR[LEFT]][nextC[LEFT]] == 0) direction = LEFT;
else if (leftRight < 0 && MAP[nextR[RIGHT]][nextC[RIGHT]] == 0) direction = RIGHT;
if (direction == -1) continue;
PLAYER[p].r = PLAYER[p].r + dr[direction];
PLAYER[p].c = PLAYER[p].c + dc[direction];
if (PLAYER[p].r == EXIT.r && PLAYER[p].c == EXIT.c) PLAYER[p].escape = ESCAPE;
step++;
}
return step;
}
int allExitCheck()
{
for (int p = 0; p < M; p++)
if (PLAYER[p].escape == 0) return 0;
return 1;
}
int rotateCheck(int map[MAX][MAX], int sr, int sc, int size)
{
int exitCheck;
int playerCheck;
exitCheck = playerCheck = 0;
for (int r = sr; r < sr + size; r++)
{
for (int c = sc; c < sc + size; c++)
{
if (map[r][c] >= MARK) playerCheck++;
else if (map[r][c] == EXIT_CHECK) exitCheck = 1;
}
}
return exitCheck && playerCheck;
}
RC getRotateInfo()
{
RC ret = { 0 };
for (int size = 2; size <= N; size++)
{
for (int r = 1; r <= N - size + 1; r++)
{
for (int c = 1; c <= N - size + 1; c++)
{
int tmpMAP[MAX][MAX] = { 0 };
copyMap(tmpMAP, MAP);
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
tmpMAP[PLAYER[p].r][PLAYER[p].c] = p + MARK;
}
tmpMAP[EXIT.r][EXIT.c] = EXIT_CHECK;
if (rotateCheck(tmpMAP, r, c, size) != 0)
{
ret.r = r;
ret.c = c;
ret.size = size;
return ret;
}
}
}
}
}
RC rotateRC(RC rc, RC rotateInfo)
{
RC ret = { 0 };
int tmpMAP[MAX][MAX] = { 0 };
tmpMAP[rc.r][rc.c] = 1;
rotate(tmpMAP, rotateInfo.r, rotateInfo.c, rotateInfo.size);
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (tmpMAP[r][c] == 1)
{
ret.r = r;
ret.c = c;
return ret;
}
}
}
ret.r = ret.c = -1; // error
return ret;
}
int isBoundary(RC rc, RC rotateInfo)
{
int sr = rotateInfo.r;
int er = rotateInfo.r + rotateInfo.size;
int sc = rotateInfo.c;
int ec = rotateInfo.c + rotateInfo.size;
return (sr <= rc.r && rc.r < er && sc <= rc.c && rc.c < ec);
}
void wallDown(RC rotateInfo)
{
for (int r = 1; r <= N; r++)
{
for (int c = 1; c <= N; c++)
{
if (MAP[r][c] == 0) continue;
RC rc = { 0 };
rc.r = r;
rc.c = c;
if (isBoundary(rc, rotateInfo) == 0) continue;
MAP[r][c]--;
}
}
}
void rotateMaze()
{
RC rotateInfo = getRotateInfo();
rotate(MAP, rotateInfo.r, rotateInfo.c, rotateInfo.size);
EXIT = rotateRC(EXIT, rotateInfo);
for (int p = 0; p < M; p++)
{
if (PLAYER[p].escape == ESCAPE) continue;
if (isBoundary(PLAYER[p], rotateInfo) == 0) continue;
PLAYER[p] = rotateRC(PLAYER[p], rotateInfo);
}
wallDown(rotateInfo);
}
int main(void)
{
// scanf("%d", &T);
T = 1;
for (int tc = 1; tc <= T; tc++)
{
input();
int sum = 0;
for (int k = 0; k < K; k++)
{
int step = move();
sum += step;
if (allExitCheck() == true) break;
rotateMaze();
}
printf("%d\n", sum);
printf("%d %d\n", EXIT.r, EXIT.c);
}
return 0;
}반응형