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

[코드트리] 술래잡기 (삼성 SW 역량테스트 2022 상반기 오전 1번)

피로물든딸기 2024. 6. 9. 21:26
반응형

삼성 A형 전체 링크

 

참고

- BOJ 1913 : 달팽이

 

https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek

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

 

필요한 변수를 선언한다.

도망자가 잡혔는지 확인하기 위해 dead 변수가 필요하지만, taggerInfo는 dead를 사용하지 않는다.

tree는 좌표만 알면 충분하므로 2차원 int 배열로 저장한다.

int N, M, H, K;

typedef struct st2
{
	int r;
	int c;
	int dir;
	int dead;
}PERSON;

int tree[MAX][MAX];

PERSON runner[MAX * MAX];
int rcnt;

PERSON taggerInfo[MAX * MAX * 2];
int tcnt;

 

달팽이 배열을 만들기 위한 방향 배열을 설정한다.

/* ↑, →, ↓, ← 상우하좌 */
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

 

input은 다음과 같다. 

참고로 도망자의 방향이 마침 달팽이 배열의 방향과 일치하기 때문에 그대로 d를 저장하면 된다.

void input()
{
	scanf("%d %d %d %d", &N, &M, &H, &K);
	
	rcnt = tcnt = 0;

	// runner
	for (int m = 0; m < M; m++)
	{
		int r, c, d;
		scanf("%d %d %d", &r, &c, &d);
		
		runner[rcnt].dead = 0; // init

		runner[rcnt].r = r;
		runner[rcnt].c = c;
		
		runner[rcnt++].dir = d;	
	}

	// tree init
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			tree[r][c] = 0;

	// tree
	for (int h = 0; h < H; h++)
	{
		int r, c;
		
		scanf("%d %d", &r, &c); 

		tree[r][c] = 1;
	}
}

구현

 

이 문제는 N이 결정되면, 술래가 있어야 할 위치와 방향이 바로 결정된다.

좌표는 (1, 1) ~ (N, N)으로 설정하고, BOJ 1913 : 달팽이를 참고하여 아래의 달팽이 배열을 만든다.

void makeSnail()
{
	int snailMap[MAX][MAX] = { 0 };

	int sr, sc, dir, index, size;

	dir = index = size = 0;
	sr = sc = N / 2 + 1;

	snailMap[sr][sc] = index++;
	
	taggerInfo[tcnt].r = sr;
	taggerInfo[tcnt++].c = sc;
 	
	for (int i = 0; i < 2 * N - 1; i++)
	{
		if (i % 2 == 0) size++;

		for (int s = 0; s < size; s++)
		{
			int nr, nc;

			nr = sr + dr[dir];
			nc = sc + dc[dir];

			snailMap[nr][nc] = index++;
			taggerInfo[tcnt].r = nr;
			taggerInfo[tcnt++].c = nc;

			sr = nr;
			sc = nc;
		}

		dir++;
		if (dir == 4) dir = 0;
	}
    
	...
}

 

N = 5라면 총 25칸에서 첫 칸과 마지막 칸은 한 번만 위치하게 된다.

따라서 위치를 거꾸로 한 번 더 복사하고, 전체 좌표의 위치의 개수는 2 * N * N - 2 가 된다.

	tcnt = N * N;
	for (int i = 0; i < tcnt; i++)
		taggerInfo[tcnt + i] = taggerInfo[tcnt - i - 2];

	tcnt = 2 * N * N - 2;

 

그래서 taggerInfo의 메모리도 MAX * MAX * 2로 잡았다.

PERSON taggerInfo[MAX * MAX * 2];
int tcnt;

 

술래의 방향은 현재 좌표와 다음 좌표를 이용하여 설정하였다.

현재 좌표보다 다음 좌표의 row가 작다면, 위에 있는 좌표이므로 dir = 0이 된다. 

	for (int i = 0; i < tcnt - 1; i++)
	{
		int r, c, nr, nc;

		r = taggerInfo[i].r;
		c = taggerInfo[i].c;
		nr = taggerInfo[i + 1].r;
		nc = taggerInfo[i + 1].c;

		if (nr - r == -1) taggerInfo[i].dir = 0;
		else if (nr - r == 1) taggerInfo[i].dir = 2;
		else if (nc - c == 1) taggerInfo[i].dir = 1;
		else if (nc - c == -1) taggerInfo[i].dir = 3;
	}

	taggerInfo[tcnt - 1].dir = 0;

 

N = 5일 때, 아래와 같은 달팽이 배열이 만들어지고, taggerInfo에 미리 술래의 위치와 방향을 저장된다.

그리고 taggerInfo를 계속 반복하기 때문에 (술래의 K 번째 턴 % tcnt)로 현재 술래의 위치와 방향을 알 수 있다.

24  9 10 11 12
23  8  1  2 13
22  7  0  3 14
21  6  5  4 15
20 19 18 17 16

0] (3, 3) / 0
1] (2, 3) / 1
2] (2, 4) / 2
3] (3, 4) / 2
4] (4, 4) / 3
5] (4, 3) / 3
6] (4, 2) / 0
7] (3, 2) / 0
8] (2, 2) / 0
9] (1, 2) / 1
10] (1, 3) / 1
11] (1, 4) / 1
12] (1, 5) / 2
13] (2, 5) / 2
14] (3, 5) / 2
15] (4, 5) / 2
16] (5, 5) / 3
17] (5, 4) / 3
18] (5, 3) / 3
19] (5, 2) / 3
20] (5, 1) / 0
21] (4, 1) / 0
22] (3, 1) / 0
23] (2, 1) / 0
24] (1, 1) / 2
25] (2, 1) / 2
26] (3, 1) / 2
27] (4, 1) / 2
28] (5, 1) / 1
29] (5, 2) / 1
30] (5, 3) / 1
31] (5, 4) / 1
32] (5, 5) / 0
33] (4, 5) / 0
34] (3, 5) / 0
35] (2, 5) / 0
36] (1, 5) / 3
37] (1, 4) / 3
38] (1, 3) / 3
39] (1, 2) / 2
40] (2, 2) / 2
41] (3, 2) / 2
42] (4, 2) / 1
43] (4, 3) / 1
44] (4, 4) / 0
45] (3, 4) / 0
46] (2, 4) / 3
47] (2, 3) / 2

 

도망자의 이동은 다음과 같다.

makeSnail에서 모든 턴에 대한 술래의 좌표를 구했으므로, k % tcnt로 현재 술래의 좌표를 가져온다.

그리고 방향을 바꾸기 위한 changeDir 배열을 만든다. (0은 2로, 2는 0으로, 1은 3, 3은 1로 바꾸는 배열)

 

도망자가 적기 때문에 매번 전체 도망자를 순회한다.

잡힌 도망자 (dead = 1)가 아니고, 술래와의 거리가 3 이하인 도망자 중,

다음으로 갈 위치 (nr, nc)가 격자를 벗어나면 방향을 바꾸고 다시 (nr, nc)를 갱신한다.

이동할 위치 (nr, nc)에 술래가 없다면 이동한다.

void moveRunner(int k)
{
	PERSON curTagger = taggerInfo[k % tcnt];
	
	int changeDir[] = { 2, 3, 0, 1 };

	for (int i = 0; i < rcnt; i++)
	{
		if (runner[i].dead == 1) continue;

		int distance = getDistance(curTagger.r, curTagger.c, runner[i].r, runner[i].c);

		// 술래와의 거리가 3 이하인 도망자만 움직인다.
		if (distance > 3) continue;

		int nr, nc;

		nr = runner[i].r + dr[runner[i].dir];
		nc = runner[i].c + dc[runner[i].dir];

		// 0 -> 2, 2 -> 0 / 1 -> 3, 3 -> 1
		// 격자를 벗어나는 경우, 방향을 바꾼다.
		if (nr < 1 || nc < 1 || nr > N || nc > N)
		{
			runner[i].dir = changeDir[runner[i].dir];
			
			// 새롭게 갈 방향 설정
			nr = runner[i].r + dr[runner[i].dir];
			nc = runner[i].c + dc[runner[i].dir];
		}

		// 술래가 있는 경우
		if (nr == curTagger.r && nc == curTagger.c) continue;

		runner[i].r = nr;
		runner[i].c = nc;
	}
}

 

참고로 거리는 다음과 같이 구할 수 있다.

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

int getDistance(int r1, int c1, int r2, int c2)
{	
	return abs(r1 - r2) + abs(c1 - c2);
}

 

술래는 k % tcnt 가 아니라 (k + 1) % tcnt 로 정보를 얻는다.

술래의 첫 번째 턴은, 술래의 첫 위치가 아니라, 처음으로 이동한 위치이기 때문이다.

격자를 벗어난 경우는 탐색을 중단하고, 나무가 있는 경우는 continue로 넘어간다.

그리고 잡히지 않은 모든 술래에 대해 같은 좌표인 술래를 찾아서 점수를 계산한다.

int moveTagger(int k)
{
	PERSON curTagger = taggerInfo[(k + 1) % tcnt];

	int catchCount = 0;

	// 시야 내 도망자 catch (현재 칸 포함 세 칸)
	for (int d = 0; d < 3; d++)
	{
		int nr, nc;

		nr = curTagger.r + dr[curTagger.dir] * d;
		nc = curTagger.c + dc[curTagger.dir] * d;

		if (nr < 1 || nc < 1 || nr > N || nc > N) break;
		if (tree[nr][nc]) continue; // 나무가 있는 경우는 도망자 catch 불가

		for (int i = 0; i < rcnt; i++)
		{
			if (runner[i].dead == 1) continue;
			if (runner[i].r == nr && runner[i].c == nc)
			{
				runner[i].dead = 1;
				catchCount++;
			}
		}
	}
	
	// 잡힌 도망자는 제거, 턴 x 잡은 도망자 수 만큼 점수 획득.
	return catchCount * (k + 1);
}

 

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (100 + 5)

int T;
int N, M, H, K;

typedef struct st2
{
	int r;
	int c;
	int dir;
	int dead;
}PERSON;

int tree[MAX][MAX];

PERSON runner[MAX * MAX];
int rcnt;

PERSON taggerInfo[MAX * MAX * 2];
int tcnt;

/* ↑, →, ↓, ← 상우하좌 */
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

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

int getDistance(int r1, int c1, int r2, int c2)
{	
	return abs(r1 - r2) + abs(c1 - c2);
}

void input()
{
	scanf("%d %d %d %d", &N, &M, &H, &K);
	
	rcnt = tcnt = 0;

	// runner
	for (int m = 0; m < M; m++)
	{
		int r, c, d;
		scanf("%d %d %d", &r, &c, &d);
		
		runner[rcnt].dead = 0; // init

		runner[rcnt].r = r;
		runner[rcnt].c = c;
		
		runner[rcnt++].dir = d;	
	}

	// tree init
	for (int r = 0; r < MAX; r++)
		for (int c = 0; c < MAX; c++)
			tree[r][c] = 0;

	// tree
	for (int h = 0; h < H; h++)
	{
		int r, c;
		
		scanf("%d %d", &r, &c); 

		tree[r][c] = 1;
	}
}

void makeSnail()
{
	int snailMap[MAX][MAX] = { 0 };

	int sr, sc, dir, index, size;

	dir = index = size = 0;
	sr = sc = N / 2 + 1;

	snailMap[sr][sc] = index++;
	
	taggerInfo[tcnt].r = sr;
	taggerInfo[tcnt++].c = sc;
 	
	for (int i = 0; i < 2 * N - 1; i++)
	{
		if (i % 2 == 0) size++;

		for (int s = 0; s < size; s++)
		{
			int nr, nc;

			nr = sr + dr[dir];
			nc = sc + dc[dir];

			snailMap[nr][nc] = index++;
			taggerInfo[tcnt].r = nr;
			taggerInfo[tcnt++].c = nc;

			sr = nr;
			sc = nc;
		}

		dir++;
		if (dir == 4) dir = 0;
	}

	tcnt = N * N;
	for (int i = 0; i < tcnt; i++)
		taggerInfo[tcnt + i] = taggerInfo[tcnt - i - 2];

	tcnt = 2 * N * N - 2;

	for (int i = 0; i < tcnt - 1; i++)
	{
		int r, c, nr, nc;

		r = taggerInfo[i].r;
		c = taggerInfo[i].c;
		nr = taggerInfo[i + 1].r;
		nc = taggerInfo[i + 1].c;

		if (nr - r == -1) taggerInfo[i].dir = 0;
		else if (nr - r == 1) taggerInfo[i].dir = 2;
		else if (nc - c == 1) taggerInfo[i].dir = 1;
		else if (nc - c == -1) taggerInfo[i].dir = 3;
	}

	taggerInfo[tcnt - 1].dir = 2;

	return;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%2d ", snailMap[r][c]);
		putchar('\n');
	}			
	putchar('\n');
	for (int i = 0; i < tcnt; i++)
		printf("%d] (%d, %d) / %d\n", i, taggerInfo[i].r, taggerInfo[i].c, taggerInfo[i].dir);
}

void moveRunner(int k)
{
	PERSON curTagger = taggerInfo[k % tcnt];
	
	int changeDir[] = { 2, 3, 0, 1 };

	for (int i = 0; i < rcnt; i++)
	{
		if (runner[i].dead == 1) continue;

		int distance = getDistance(curTagger.r, curTagger.c, runner[i].r, runner[i].c);

		// 술래와의 거리가 3 이하인 도망자만 움직인다.
		if (distance > 3) continue;

		int nr, nc;

		nr = runner[i].r + dr[runner[i].dir];
		nc = runner[i].c + dc[runner[i].dir];

		// 0 -> 2, 2 -> 0 / 1 -> 3, 3 -> 1
		// 격자를 벗어나는 경우, 방향을 바꾼다.
		if (nr < 1 || nc < 1 || nr > N || nc > N)
		{
			runner[i].dir = changeDir[runner[i].dir];
			
			// 새롭게 갈 방향 설정
			nr = runner[i].r + dr[runner[i].dir];
			nc = runner[i].c + dc[runner[i].dir];
		}

		// 술래가 있는 경우
		if (nr == curTagger.r && nc == curTagger.c) continue;

		runner[i].r = nr;
		runner[i].c = nc;
	}
}

int moveTagger(int k)
{
	PERSON curTagger = taggerInfo[(k + 1) % tcnt];

	int catchCount = 0;

	// 시야 내 도망자 catch (현재 칸 포함 세 칸)
	for (int d = 0; d < 3; d++)
	{
		int nr, nc;

		nr = curTagger.r + dr[curTagger.dir] * d;
		nc = curTagger.c + dc[curTagger.dir] * d;

		if (nr < 1 || nc < 1 || nr > N || nc > N) break;
		if (tree[nr][nc]) continue; // 나무가 있는 경우는 도망자 catch 불가

		for (int i = 0; i < rcnt; i++)
		{
			if (runner[i].dead == 1) continue;
			if (runner[i].r == nr && runner[i].c == nc)
			{
				runner[i].dead = 1;
				catchCount++;
			}
		}
	}
	
	// 잡힌 도망자는 제거, 턴 x 잡은 도망자 수 만큼 점수 획득.
	return catchCount * (k + 1);
}

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

		makeSnail();
		
		int totalScore = 0;
		for (int k = 0; k < K; k++)
		{
			moveRunner(k);
			totalScore += moveTagger(k);			
		}

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

	return 0;
}
반응형