[코드트리] 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번)

알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 메이즈 러너 (삼성 SW 역량테스트 2023 상반기 오후 1번)

피로물든딸기 2024. 7. 31. 01:24

삼성 A형 전체 링크

참고

- 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;
}