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

[코드트리] 코드트리 빵 (삼성 SW 역량테스트 2022 하반기 오후 1번)

피로물든딸기 2024. 7. 19. 01:00
반응형

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread

이후 설명 및 입/출력은 링크 참고

 

좌표를 관리하기 위한 구조체를 선언한다.

depth는 베이스 캠프에서만 사용한다.

typedef struct st
{
	int r;
	int c;
	int depth; // for base camp 
}RC;

RC BASECAMP[MAX * MAX];
int bcnt;

RC STORE[MAX * MAX];
RC PLAYER[MAX * MAX];

 

사용된 베이스 캠프와 도착한 편의점을 체크하기 위해 2차원 배열을 선언한다.

int BLOCK[MAX][MAX];

 

2차원 탐색을 위한 배열은 다음과 같다.

// ↑, ←, →, ↓
int dr[] = { -1, 0, 0, 1 };
int dc[] = { 0, -1, 1, 0 };

 

input 및 초기화는 다음과 같다.

void input()
{
	scanf("%d %d\n", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = BLOCK[r][c] = 0;

	bcnt = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c]);
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1) 
			{
				BASECAMP[bcnt].r = r;
				BASECAMP[bcnt++].c = c;
			}
		}
	}

	for (int m = 1; m <= M; m++)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		STORE[m].r = x;
		STORE[m].c = y;
	}
}

 

main은 input 입력 후 시뮬레이션을 실행한다.

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int ret = simulate();

		printf("%d\n", ret);
	}

	return 0;
}

구현

 

시뮬레이션은 다음과 같이 진행된다.

 

1. time 보다 작은 player가 어디로 이동할지 기록한다. (편의점과 좌표가 동일한 player는 continue)

2. 한 번에 이동하면서 편의점에 도착한 player를 count하고, 모두 이동한 경우는 종료한다.

3. 시간을 증가한다. (time++)

4. time에 해당하는 player를 basecamp에 할당한다.

int simulate()
{
	int time = 0;
	while (1)
	{
		// 1. time 보다 작은 player ↑, ←, →, ↓ 1칸 이동
		// 다음으로 이동할 칸을 nextSteps에 적은 후
		RC nextSteps[30 + 5] = { 0 };
		for (int p = 1; p <= time; p++)
		{
			if (p > M) break;

			// 2. 편의점에 도착한 player는 이동하지 않음.
			if (PLAYER[p].r == STORE[p].r && PLAYER[p].c == STORE[p].c) continue;
			
		}

		// 1. 한 번에 이동
		int count = 0;
		for (int p = 1; p <= time; p++)
		{
			if (p > M) break;

			// 2. 편의점에 도착한 player counting
			...
		}

		if (count == M) return time; // 편의점에 모두 도착한 경우 종료

		time++; // 1, 2 이후 시간을 증가.

		// 3. time 에 해당하는 player를 basecamp에 할당.
		...
	}

	return 0;
}

베이스 캠프 할당

 

basecamp 할당은 다음과 같다.

	// 3. time 에 해당하는 player를 basecamp에 할당.
	if (time <= M)
	{
		RC rc = getBaseCamp(time);
		setBaseCamp(rc); // 사용된 베이스캠프 처리

		PLAYER[time].r = rc.r; // player 시작점
		PLAYER[time].c = rc.c;
	}

 

getBaseCamp는 다음과 같다.

 

1) 베이스 캠프를 찾으려는 player가 가려고 하는 편의점의 위치 (sr, sc)를 기준으로 모든 베이스 캠프를 찾는다.

(먼저 찾는 베이스 캠프가 정답이라는 보장이 없다.)

2) queue에 넣을 때, 해당 좌표까지 가기 위한 거리 depth를 기록한다.

3) 모든 후보지에서 문제의 조건인 행과 열이 작은 가장 가까운 베이스 캠프를 찾는다.

 

이미 할당된 베이스 캠프는 BLOCK에서 관리해야 한다.

RC getBaseCamp(int playerNumber)
{
	RC ret;
	RC basecamp[MAX * MAX] = { 0 }; // 후보
	int campCount = 0;
	int count;

	RC queue[MAX * MAX];
	int wp, rp;
	int visit[MAX][MAX] = { 0 };

	wp = rp = 0;

	int sr = STORE[playerNumber].r;
	int sc = STORE[playerNumber].c;

	queue[wp].r = sr;
	queue[wp].c = sc;
	queue[wp++].depth = 0;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		RC out = queue[rp++];
		if (MAP[out.r][out.c] == 1 && BLOCK[out.r][out.c] == 0) // basecamp를 찾은 경우, 모두 후보지에 등록
		{
			basecamp[campCount].r = out.r;
			basecamp[campCount].c = out.c;
			basecamp[campCount++].depth = out.depth;

			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && BLOCK[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].depth = out.depth + 1;

				visit[nr][nc] = 1;
			}
		}
	}

	ret.r = ret.c = 0x7fff0000;
	int maxDistance = 0x7fff0000;
	for (int i = 0; i < campCount; i++)
	{
		if (basecamp[i].depth < maxDistance)
		{
			maxDistance = basecamp[i].depth;

			ret.r = basecamp[i].r;
			ret.c = basecamp[i].c;
		}
		else if (basecamp[i].depth == maxDistance)
		{
			if (basecamp[i].r < ret.r)
			{
				ret.r = basecamp[i].r;
				ret.c = basecamp[i].c;
			}
			else if (basecamp[i].r == ret.r)
			{
				if (basecamp[i].c < ret.c)
				{
					ret.r = basecamp[i].r;
					ret.c = basecamp[i].c;
				}
			}
		}
	}

	return ret;
}

 

할당된 캠프는 set에서 처리하자.

void setBaseCamp(RC rc)
{
	for (int b = 0; b < bcnt; b++)
	{
		if (BASECAMP[b].r == rc.r && BASECAMP[b].c == rc.c)
		{
			BLOCK[rc.r][rc.c] = 1;
			return;
		}
	}
}

Player의 다음 좌표 찾기

 

time 보다 작은 모든 플레이어를 움직일 때, player의 다음 좌표를 찾아야 한다.

문제에 의하면, player의 이동 경로는 매번 바뀔 수 있다.

player가 추가되면 베이스 캠프를 통과할 수 없고, 편의점에 도착하면 편의점도 통과할 수 없기 때문이다.

	while (1)
	{
		// 1. time 보다 작은 player ↑, ←, →, ↓ 1칸 이동
		// 다음으로 이동할 칸을 nextSteps에 적은 후
		RC nextSteps[30 + 5] = { 0 };
		for (int p = 1; p <= time; p++)
		{
			if (p > M) break;

			// 2. 편의점에 도착한 player는 이동하지 않음.
			if (PLAYER[p].r == STORE[p].r && PLAYER[p].c == STORE[p].c) continue;

			RC next = getNextStep(p);
			
			nextSteps[p].r = next.r;
			nextSteps[p].c = next.c;
		}
        
		...

 

getNextStep은 다음과 같다.

BFS를 이용해 Player의 좌표 (sr, sc)에서 편의점 좌표 (er, ec)로 이동한다.

이때 before 배열에 이전 좌표를 기록하면 경로를 기억할 수 있다.

따라서 최단 거리에서 가장 첫 번째 좌표을 while 문으로 거꾸로 돌아간 후, 해당 좌표를 return하면 된다.

RC getNextStep(int playerNumber)
{
	RC ret;
	RC queue[MAX * MAX];
	int wp, rp;

	int visit[MAX][MAX] = { 0 };
	RC before[MAX][MAX] = { 0 };

	wp = rp = 0;

	int sr = PLAYER[playerNumber].r;
	int sc = PLAYER[playerNumber].c;
	int er = STORE[playerNumber].r;
	int ec = STORE[playerNumber].c;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	before[sr][sc].r = -1;
	before[sr][sc].c = -1;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		RC out = queue[rp++];

		if (er == out.r && ec == out.c)
		{
			int tr = out.r;
			int tc = out.c;
			while (1)
			{
				// 이전 좌표
				int br = before[tr][tc].r;
				int bc = before[tr][tc].c;

				if (br == sr && bc == sc) break;

				tr = br;
				tc = bc;
			}

			ret.r = tr;
			ret.c = tc;

			return ret;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && BLOCK[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				before[nr][nc].r = out.r; // 이전 좌표 기억
				before[nr][nc].c = out.c;

				visit[nr][nc] = 1;
			}
		}
	}

	// error
	ret.r = ret.c = -1;

	return ret;
}

 

모든 좌표를 구했다면, 한 번에 이동해야 한다.

이동 후, 편의점에 도착한 player의 좌표를 BLOCK에 표시한다.

	// 1. 한 번에 이동
	int count = 0;
	for (int p = 1; p <= time; p++)
	{
		if (p > M) break;

		// 2. 편의점에 도착한 player counting
		if (PLAYER[p].r == STORE[p].r && PLAYER[p].c == STORE[p].c)
		{
			count++;
			continue;
		}

		int nr = nextSteps[p].r;
		int nc = nextSteps[p].c;

		PLAYER[p].r = nr;
		PLAYER[p].c = nc;

		// 편의점에 도착한 경우 편의점 칸은 이동 불가 처리
		if (nr == STORE[p].r && nc == STORE[p].c)
			BLOCK[nr][nc] = 1;
	}

 

그 외 코드는 전체 코드를 참고하자.

#include <stdio.h>

#define MAX (15 + 5)

int T;
int N, M;

int MAP[MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int depth;
}RC;

RC BASECAMP[MAX * MAX];
int bcnt;

RC STORE[MAX * MAX];
RC PLAYER[MAX * MAX];

int BLOCK[MAX][MAX];

// ↑, ←, →, ↓
int dr[] = { -1, 0, 0, 1 };
int dc[] = { 0, -1, 1, 0 };

void input()
{
	scanf("%d %d\n", &N, &M);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = BLOCK[r][c] = 0;

	bcnt = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c]);
		}
	}

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == 1) 
			{
				BASECAMP[bcnt].r = r;
				BASECAMP[bcnt++].c = c;				
			}
		}
	}

	for (int m = 1; m <= M; m++)
	{
		int x, y;

		scanf("%d %d", &x, &y);

		STORE[m].r = x;
		STORE[m].c = y;
	}
}

void printMap()
{
	int temp[MAX][MAX] = { 0 };

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			temp[r][c] = MAP[r][c];

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (temp[r][c] == 1) temp[r][c] = -1;

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			if (BLOCK[r][c] == 1) temp[r][c] = -2;


	for (int p = 1; p <= M; p++) temp[PLAYER[p].r][PLAYER[p].c] = p;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%2d ", temp[r][c]);
		putchar('\n');
	}
}

int abs(int x)
{
	return (x > 0) ? x : -x;
}

RC getNextStep(int playerNumber)
{
	RC ret;
	RC queue[MAX * MAX];
	int wp, rp;

	int visit[MAX][MAX] = { 0 };
	RC before[MAX][MAX] = { 0 };

	wp = rp = 0;

	int sr = PLAYER[playerNumber].r;
	int sc = PLAYER[playerNumber].c;
	int er = STORE[playerNumber].r;
	int ec = STORE[playerNumber].c;

	queue[wp].r = sr;
	queue[wp++].c = sc;

	before[sr][sc].r = -1;
	before[sr][sc].c = -1;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		RC out = queue[rp++];

		if (er == out.r && ec == out.c)
		{
			int tr = out.r;
			int tc = out.c;
			while (1)
			{
				// 이전 좌표
				int br = before[tr][tc].r;
				int bc = before[tr][tc].c;

				if (br == sr && bc == sc) break;

				tr = br;
				tc = bc;
			}

			ret.r = tr;
			ret.c = tc;

			return ret;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && BLOCK[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp++].c = nc;

				before[nr][nc].r = out.r; // 이전 좌표 기억
				before[nr][nc].c = out.c;

				visit[nr][nc] = 1;
			}
		}
	}

	// error
	ret.r = ret.c = -1;

	return ret;
}

RC getBaseCamp(int playerNumber)
{
	RC ret;
	RC basecamp[MAX * MAX] = { 0 }; // 후보
	int campCount = 0;
	int count;

	RC queue[MAX * MAX];
	int wp, rp;
	int visit[MAX][MAX] = { 0 };

	wp = rp = 0;

	int sr = STORE[playerNumber].r;
	int sc = STORE[playerNumber].c;

	queue[wp].r = sr;
	queue[wp].c = sc;
	queue[wp++].depth = 0;

	visit[sr][sc] = 1;

	while (wp > rp)
	{
		RC out = queue[rp++];
		if (MAP[out.r][out.c] == 1 && BLOCK[out.r][out.c] == 0) // basecamp를 찾은 경우, 모두 후보지에 등록
		{
			basecamp[campCount].r = out.r;
			basecamp[campCount].c = out.c;
			basecamp[campCount++].depth = out.depth;

			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (visit[nr][nc] == 0 && BLOCK[nr][nc] == 0)
			{
				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].depth = out.depth + 1;

				visit[nr][nc] = 1;
			}
		}
	}

	ret.r = ret.c = 0x7fff0000;
	int maxDistance = 0x7fff0000;
	for (int i = 0; i < campCount; i++)
	{
		if (basecamp[i].depth < maxDistance)
		{
			maxDistance = basecamp[i].depth;

			ret.r = basecamp[i].r;
			ret.c = basecamp[i].c;
		}
		else if (basecamp[i].depth == maxDistance)
		{
			if (basecamp[i].r < ret.r)
			{
				ret.r = basecamp[i].r;
				ret.c = basecamp[i].c;
			}
			else if (basecamp[i].r == ret.r)
			{
				if (basecamp[i].c < ret.c)
				{
					ret.r = basecamp[i].r;
					ret.c = basecamp[i].c;
				}
			}
		}
	}

	return ret;
}

void setBaseCamp(RC rc)
{
	for (int b = 0; b < bcnt; b++)
	{
		if (BASECAMP[b].r == rc.r && BASECAMP[b].c == rc.c)
		{
			BLOCK[rc.r][rc.c] = 1;
			return;
		}
	}
}

int simulate()
{
	int time = 0;
	while (1)
	{
		// 1. time 보다 작은 player ↑, ←, →, ↓ 1칸 이동
		// 다음으로 이동할 칸을 nextSteps에 적은 후
		RC nextSteps[30 + 5] = { 0 };
		for (int p = 1; p <= time; p++)
		{
			if (p > M) break;

			// 2. 편의점에 도착한 player는 이동하지 않음.
			if (PLAYER[p].r == STORE[p].r && PLAYER[p].c == STORE[p].c) continue;

			RC next = getNextStep(p);
			
			nextSteps[p].r = next.r;
			nextSteps[p].c = next.c;
		}

		// 1. 한 번에 이동
		int count = 0;
		for (int p = 1; p <= time; p++)
		{
			if (p > M) break;

			// 2. 편의점에 도착한 player counting
			if (PLAYER[p].r == STORE[p].r && PLAYER[p].c == STORE[p].c)
			{
				count++;
				continue;
			}

			int nr = nextSteps[p].r;
			int nc = nextSteps[p].c;

			PLAYER[p].r = nr;
			PLAYER[p].c = nc;

			// 편의점에 도착한 경우 편의점 칸은 이동 불가 처리
			if (nr == STORE[p].r && nc == STORE[p].c)
				BLOCK[nr][nc] = 1;
		}

		if (count == M) return time; // 편의점에 모두 도착한 경우 종료

		time++; // 1, 2 이후 시간을 증가.

		// 3. time 에 해당하는 player를 basecamp에 할당.
		if (time <= M)
		{
			RC rc = getBaseCamp(time);
			setBaseCamp(rc); // 사용된 베이스캠프 처리

			PLAYER[time].r = rc.r; // player 시작점
			PLAYER[time].c = rc.c;
		}
	}

	return 0;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		int ret = simulate();

		printf("%d\n", ret);
	}

	return 0;
}
반응형