본문 바로가기
알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 미생물 연구 (삼성 SW 역량테스트 2025 상반기 오후 1번)

by 피로물든딸기 2025. 4. 19.
반응형

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

 

삼성 A형 전체 링크

 

참고

- BOJ 2667 : 단지번호붙이기

- BOJ 14500 : 테트로미노 (삼성 SW TEST A형)

- 예술성 (삼성 SW 역량테스트 2022 상반기 오전 2번)

 

https://www.codetree.ai/ko/frequent-problems/problems/microbial-research/description

 

입력 좌표는 다음 구조체로 받아서 저장한다.

struct QUERY
{
	int r1;
	int c1;
	int r2;
	int c2;
};

QUERY query[MAX_Q];

 

미생물은 미생물의 번호(ID), 미생물이 차지하는 칸의 최소, 최대 좌표, 그리고 영역의 넓이가 필요하다.

살아있는 미생물의 개수는 mcnt로 관리하고, 미생물의 ID를 이용해 생존 여부를 관리(dead)한다.

struct MICRO
{
	int id;
	int minR;
	int minC;
	int maxR;
	int maxC;
	int count;
};

MICRO micro[MAX_Q];
int mcnt;

bool dead[MAX_Q]; // id로 따로 관리

 

필요한 변수와 input은 다음과 같다.

#define MAX (15 + 5)
#define MAX_Q (50 + 5)

int T;
int N, Q;
int MAP[MAX][MAX];

struct QUERY
{
	int r1;
	int c1;
	int r2;
	int c2;
};

QUERY query[MAX_Q];

struct MICRO
{
	int id;
	int minR;
	int minC;
	int maxR;
	int maxC;
	int count;
};

MICRO micro[MAX_Q];
int mcnt;

bool dead[MAX_Q]; // id로 따로 관리

struct RC
{
	int r;
	int c;
};

RC queue[MAX * MAX];
bool visit[MAX][MAX];

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

void input()
{
	scanf("%d %d", &N, &Q);

	// 미생물 번호는 1번부터
	for (int q = 1; q <= Q; q++)
		scanf("%d %d %d %d", &query[q].r1, &query[q].c1, &query[q].r2, &query[q].c2);
}

미생물 투입

 

미생물을 투입한다. 

주어진 입력 (r2, c2)에서 -1을 뺀 만큼 투입해야 한다.

void insert(int id, int r1, int c1, int r2, int c2)
{
	for (int r = r1; r < r2; r++)
		for (int c = c1; c < c2; c++)
			MAP[r][c] = id;
}

배양 용기 이동

 

배양 용기 이동은 다음과 같은 세 개의 함수로 나누어서 처리한다.

findLiveMicro();		
sort();
moveAll();

 

먼저, 살아있는 미생물을 찾는다.

mcnt을 0으로 초기화하고, visit 배열을 초기화한다.

check 배열을 하나 만들어서 MAP에서 중복되는 미생물을 체크한다.

즉, check[미생물 ID] 가 true인데 또 찾게 되면, 해당 미생물은 2개로 분리되었으므로 사망 처리해야 한다.

micro 배열에 mcnt 인덱스를 이용해 미생물을 추가하고, 마지막에 다시 살아있는 미생물만 정리한다.

void findLiveMicro()
{
	mcnt = 0;

	for (int r = 0; r <= N; r++)
		for (int c = 0; c <= N; c++)
			visit[r][c] = false;

	bool check[MAX_Q] = { false };
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			int id = MAP[r][c];
			
			if (id == 0 || dead[id] == true || visit[r][c] == true) continue;
			
			MICRO m = BFS(r, c);
			
			if (check[id] == true)
			{
				dead[id] = true;
				continue;
			}
						
			check[id] = true;
			micro[mcnt++] = m; 
		}
	}
	
	int tcnt = mcnt;

	mcnt = 0;
	for (int i = 0; i < tcnt; i++)
	{
		if (dead[micro[i].id] == true) continue;

		micro[mcnt++] = micro[i];
	}
}

 

미생물은 단지번호붙이기를 응용하여 영역을 구분하면 된다.

해당 영역의 최소, 최대 좌표를 갱신하고, 영역을 counting하여 MICRO를 리턴하였다.

MICRO BFS(int r, int c)
{
	int rp, wp;
	int minR, minC, maxR, maxC;

	rp = wp = 0;

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

	visit[r][c] = true;

	minR = maxR = r;
	minC = maxC = c;

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

		for (int i = 0; i < 4; i++)
		{
			int nr, nc;

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

			if (MAP[out.r][out.c] != MAP[nr][nc] || visit[nr][nc] == true) continue;

			queue[wp].r = nr;
			queue[wp++].c = nc;

			visit[nr][nc] = true;

			if (nr < minR) minR = nr;
			if (nc < minC) minC = nc;
			if (nr > maxR) maxR = nr;
			if (nc > maxC) maxC = nc;
		}
	}

	MICRO ret = { 0 };

	ret.id = MAP[r][c];
	ret.minR = minR;
	ret.minC = minC;
	ret.maxR = maxR;
	ret.maxC = maxC;
	ret.count = wp;

	return ret;
}

 

살아남은 미생물은 문제에서 제공한 우선순위에 따라 정렬하면 된다.

// a가 우선순위가 더 높으면 true
bool isPriority(MICRO a, MICRO b)
{
	if (a.count != b.count) return a.count > b.count;
	
	return a.id < b.id;
}

void sort()
{
	for (int i = 0; i < mcnt - 1; i++)
	{
		for (int k = i + 1; k < mcnt; k++)
		{
			if (isPriority(micro[i], micro[k]) == false)
			{
				MICRO tmp = micro[i];
				micro[i] = micro[k];
				micro[k] = tmp;
			}
		}
	}
}

 

그리고 새 배양 용기(newMAP)에 살아있는 미생물을 순서대로 옮긴다.

모두 옮긴 후, 새 배양 용기를 기존 배양 용기(MAP)에 복사한다.

void moveAll()
{
	int newMAP[MAX][MAX] = { 0 }; // 새 배양 용기

	for (int i = 0; i < mcnt; i++) moveMicro(newMAP, micro[i]);

	for (int r = 0; r <= N; r++)
		for (int c = 0; c <= N; c++)
			MAP[r][c] = newMAP[r][c];
}

 

moveMicro는 해당 미생물을 newMAP에 옮기는 함수다.

가장 작은 row부터, 같은 row면 가장 작은 col부터 checkMove를 이용해 옮길 수 있는지 먼저 확인한다.

옮길 수 있다면 move로 옮기면 된다.

void moveMicro(int newMAP[MAX][MAX], MICRO m)
{
	for (int r = 0; r <= N; r++)
	{
		for (int c = 0; c <= N; c++)
		{
			if (checkMove(newMAP, m, r, c) == true)
			{
				move(newMAP, m, r, c);				
				return;
			}
		}
	}
}

 

checkMove는 다음과 같다.

미생물의 최소, 최대 좌표를 이용해서 미생물이 실제로 있는 칸을 newMAP에 옮길 수 있는지 체크하면 된다.

격자 밖을 넘어가지 않는지 체크해야하는 것도 잊으면 안된다.

이런 구현은 테트로미노와 유사하다.

bool checkMove(int newMAP[MAX][MAX], MICRO m, int fr, int fc)
{
	int sr = m.minR;
	int sc = m.minC;
	int er = m.maxR;
	int ec = m.maxC;

	for (int r = sr; r <= er; r++)
	{
		for (int c = sc; c <= ec; c++)
		{
			// 미생물 범위에 다른 미생물인 경우, 빈 공간인 경우는 무시
			if (MAP[r][c] != m.id || MAP[r][c] == 0) continue;

			int newR = fr - sr + r;
			int newC = fc - sc + c;

			// 격자 밖을 넘어가는 경우
			if (newR >= N || newC >= N) return false;

			// 새 용기에 이미 다른 생물이 있는 경우
			if (newMAP[newR][newC] != 0) return false;
		}
	}

	return true;
}

 

move는 실제 미생물이 있는 칸만 옮기면 된다.

void move(int newMAP[MAX][MAX], MICRO m, int fr, int fc)
{
	int sr = m.minR;
	int sc = m.minC;
	int er = m.maxR;
	int ec = m.maxC;

	for (int r = sr; r <= er; r++)
	{
		for (int c = sc; c <= ec; c++)
		{
			if (MAP[r][c] != m.id || MAP[r][c] == 0) continue;

			newMAP[fr - sr + r][fc - sc + c] = m.id;
		}
	}
}

실험 결과 기록

 

실험 결과 기록은 예술성에서 harmony를 구한 방식과 비슷하다.

미생물이 있는 칸을 찾아서 네 방향에 다른 미생물이 있는지 company에 마킹하고 점수를 계산하였다.

int getScore(int maxID)
{
	int company[MAX_Q][MAX_Q] = { 0 };
	for (int r = 0; r <= N; r++)
	{
		for (int c = 0; c <= N; c++)
		{
			if (MAP[r][c] == 0) continue;

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				int id1 = MAP[r][c];
				int id2 = MAP[nr][nc];

				if (id1 == id2 || id2 == 0) continue;

				company[id1][id2] = true;
				company[id2][id1] = true;
			}
		}
	}
	
	int score = 0;
	for (int i = 1; i <= maxID - 1; i++)
	{
		for (int k = i + 1; k <= maxID; k++)
		{
			if (company[i][k] == false) continue;

			int count1 = getCount(i);
			int count2 = getCount(k);

			score += (count1 * count2);
		}
	}

	return score;
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (15 + 5)
#define MAX_Q (50 + 5)

int T;
int N, Q;
int MAP[MAX][MAX];

struct QUERY
{
	int r1;
	int c1;
	int r2;
	int c2;
};

QUERY query[MAX_Q];

struct MICRO
{
	int id;
	int minR;
	int minC;
	int maxR;
	int maxC;
	int count;
};

MICRO micro[MAX_Q];
int mcnt;

bool dead[MAX_Q]; // id로 따로 관리

struct RC
{
	int r;
	int c;
};

RC queue[MAX * MAX];
bool visit[MAX][MAX];

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

void input()
{
	scanf("%d %d", &N, &Q);

	// 미생물 번호는 1번부터
	for (int q = 1; q <= Q; q++)
		scanf("%d %d %d %d", &query[q].r1, &query[q].c1, &query[q].r2, &query[q].c2);
}

void printMap(int map[MAX][MAX]) // for debug
{
	for (int r = 0; r <= N; r++)
	{
		for (int c = 0; c <= N; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void printMicro(MICRO m)
{
	printf("id %d] (%d, %d) ~ (%d, %d) / count %d [dead=%d]\n",
		m.id, m.minR, m.minC, m.maxR, m.maxC, m.count, dead[m.id]);
}

void printMicroAll()
{
	for (int i = 0; i < mcnt; i++) printMicro(micro[i]);
}

void insert(int id, int r1, int c1, int r2, int c2)
{
	for (int r = r1; r < r2; r++)
		for (int c = c1; c < c2; c++)
			MAP[r][c] = id;
}

MICRO BFS(int r, int c)
{
	int rp, wp;
	int minR, minC, maxR, maxC;

	rp = wp = 0;

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

	visit[r][c] = true;

	minR = maxR = r;
	minC = maxC = c;

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

		for (int i = 0; i < 4; i++)
		{
			int nr, nc;

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

			if (MAP[out.r][out.c] != MAP[nr][nc] || visit[nr][nc] == true) continue;

			queue[wp].r = nr;
			queue[wp++].c = nc;

			visit[nr][nc] = true;

			if (nr < minR) minR = nr;
			if (nc < minC) minC = nc;
			if (nr > maxR) maxR = nr;
			if (nc > maxC) maxC = nc;
		}
	}

	MICRO ret = { 0 };

	ret.id = MAP[r][c];
	ret.minR = minR;
	ret.minC = minC;
	ret.maxR = maxR;
	ret.maxC = maxC;
	ret.count = wp;

	return ret;
}

void findLiveMicro()
{
	mcnt = 0;

	for (int r = 0; r <= N; r++)
		for (int c = 0; c <= N; c++)
			visit[r][c] = false;

	bool check[MAX_Q] = { false };
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			int id = MAP[r][c];
			
			if (id == 0 || dead[id] == true || visit[r][c] == true) continue;
			
			MICRO m = BFS(r, c);
			
			if (check[id] == true)
			{
				dead[id] = true;
				continue;
			}
						
			check[id] = true;
			micro[mcnt++] = m; 
		}
	}
	
	int tcnt = mcnt;

	mcnt = 0;
	for (int i = 0; i < tcnt; i++)
	{
		if (dead[micro[i].id] == true) continue;

		micro[mcnt++] = micro[i];
	}
}

// a가 우선순위가 더 높으면 true
bool isPriority(MICRO a, MICRO b)
{
	if (a.count != b.count) return a.count > b.count;
	
	return a.id < b.id;
}

void sort()
{
	for (int i = 0; i < mcnt - 1; i++)
	{
		for (int k = i + 1; k < mcnt; k++)
		{
			if (isPriority(micro[i], micro[k]) == false)
			{
				MICRO tmp = micro[i];
				micro[i] = micro[k];
				micro[k] = tmp;
			}
		}
	}
}

bool checkMove(int newMAP[MAX][MAX], MICRO m, int fr, int fc)
{
	int sr = m.minR;
	int sc = m.minC;
	int er = m.maxR;
	int ec = m.maxC;

	for (int r = sr; r <= er; r++)
	{
		for (int c = sc; c <= ec; c++)
		{
			// 미생물 범위에 다른 미생물인 경우, 빈 공간인 경우는 무시
			if (MAP[r][c] != m.id || MAP[r][c] == 0) continue;

			int newR = fr - sr + r;
			int newC = fc - sc + c;

			// 격자 밖을 넘어가는 경우
			if (newR >= N || newC >= N) return false;

			// 새 용기에 이미 다른 생물이 있는 경우
			if (newMAP[newR][newC] != 0) return false;
		}
	}

	return true;
}

void move(int newMAP[MAX][MAX], MICRO m, int fr, int fc)
{
	int sr = m.minR;
	int sc = m.minC;
	int er = m.maxR;
	int ec = m.maxC;

	for (int r = sr; r <= er; r++)
	{
		for (int c = sc; c <= ec; c++)
		{
			if (MAP[r][c] != m.id || MAP[r][c] == 0) continue;

			newMAP[fr - sr + r][fc - sc + c] = m.id;
		}
	}
}

void moveMicro(int newMAP[MAX][MAX], MICRO m)
{
	for (int r = 0; r <= N; r++)
	{
		for (int c = 0; c <= N; c++)
		{
			if (checkMove(newMAP, m, r, c) == true)
			{
				move(newMAP, m, r, c);				
				return;
			}
		}
	}
}

void moveAll()
{
	int newMAP[MAX][MAX] = { 0 }; // 새 배양 용기

	for (int i = 0; i < mcnt; i++) moveMicro(newMAP, micro[i]);

	for (int r = 0; r <= N; r++)
		for (int c = 0; c <= N; c++)
			MAP[r][c] = newMAP[r][c];
}

int getCount(int id)
{
	for (int i = 0; i < mcnt; i++)
		if (micro[i].id == id) return micro[i].count;

	return -1; // for debug
}

int getScore(int maxID)
{
	int company[MAX_Q][MAX_Q] = { 0 };
	for (int r = 0; r <= N; r++)
	{
		for (int c = 0; c <= N; c++)
		{
			if (MAP[r][c] == 0) continue;

			for (int i = 0; i < 4; i++)
			{
				int nr, nc;

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

				int id1 = MAP[r][c];
				int id2 = MAP[nr][nc];

				if (id1 == id2 || id2 == 0) continue;

				company[id1][id2] = true;
				company[id2][id1] = true;
			}
		}
	}
	
	int score = 0;
	for (int i = 1; i <= maxID - 1; i++)
	{
		for (int k = i + 1; k <= maxID; k++)
		{
			if (company[i][k] == false) continue;

			int count1 = getCount(i);
			int count2 = getCount(k);

			score += (count1 * count2);
		}
	}

	return score;
}

void simulate()
{
	for (int id = 1; id <= Q; id++)
	{
		int r1, c1, r2, c2;

		r1 = query[id].r1;
		c1 = query[id].c1;
		r2 = query[id].r2;
		c2 = query[id].c2;

		// 미생물 투입
		insert(id, r1, c1, r2, c2);				

		// 배양 용기 이동
		findLiveMicro();
		sort();
		moveAll();

		// 실험 결과 기록
		printf("%d\n", getScore(id));
	}
}

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

		simulate();
	}

	return 0;
}
반응형

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

[코드트리] 여왕 개미 (삼성 SW 역량테스트 2025 상반기 오후 2번, B형)  (0) 2025.04.23
[코드트리] 민트 초코 우유 (삼성 SW 역량테스트 2025 상반기 오전 1번)  (0) 2025.04.15
[코드트리] 코드트리 등산 게임 (삼성 SW 역량테스트 2024 하반기 오후 2번, B형)  (2) 2024.12.20
[코드트리] 메두사와 전사들 (삼성 SW 역량테스트 2024 하반기 오후 1번)  (0) 2024.12.20
[코드트리] 코드트리 DB (삼성 SW 역량테스트 2024 하반기 오전 2번, B형)  (0) 2024.12.20

관련글

댓글

티스토리툴바