[코드트리] 여왕 개미 (삼성 SW 역량테스트 2025 상반기 오후 2번, B형)

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

삼성 B형 전체 링크

 

2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,

A형 1문제 + B형 문제 1문제가 출제됩니다.

 

https://www.codetree.ai/ko/frequent-problems/problems/queen-ant/description

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

 

구현 내용은 다음과 같다.

 

1. 마을 건설

- 입력받은 순서대로 배열과 인덱스를 활용하여 집의 위치를 추가하면 된다.

 

2. 개미집 건설

- 건설할 개미집은 현재 건설된 개미집의 좌표보다 크기 때문에 마을 건설과 마찬가지로 집의 위치를 추가하면 된다.

 

3. 개미집 철거

- 철거할 개미집도 위치가 아니라 q번째 집이 주어지므로 bool 배열로 관리하면 된다.

 

4. 개미집 정찰

- 개미가 이동하는 최소 거리(= 시간)는 가장 작은 경우 0이고 가장 큰 경우 10⁹이다.

- 따라서 이분 탐색을 이용해 특정 시간에 대해 개미가 움직일 수 있는지 시뮬레이션하고 최적의 정답을 찾으면 된다.

---

마을 건설

 

house에 마을의 위치를 기록하고, isBroken으로 철거 유무를 판단한다.

#define MAX (20000 + 10000 + 500)

int house[MAX];
bool isBroken[MAX];
int hcnt = 0;

 

여왕 개미의 집이 0번 index이기 때문에 hcnt는 1부터 시작하였다.

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

	hcnt = 1; // 여왕 개미의 집 house[0] = 0;
	for (int i = 0; i < N; i++)
	{
		int x;

		scanf("%d", &x);

		house[hcnt++] = x;
	}

	for (int i = 0; i < MAX; i++) isBroken[i] = false;
}

---

개미집 건설

 

index를 이용해 배열에 개미집의 위치를 추가하면 된다.

void createAntHouse(int pos)
{
	house[hcnt++] = pos;
}

---

개미집 철거

 

bool 배열로 q번째 개미집을 철거하였다.

void removeAntHouse(int index)
{
	isBroken[index] = true;
}

---

개미집 정찰

 

개미가 이동에 필요한 시간이 가장 작은 경우는 0, 최악의 경우는 큰 경우 10⁹(= INF)이다.

따라서 이 값을 left와 right로 설정한다.

	left = 0;
	right = INF;

 

이제 left와 right의 절반의 값인 mid 시간동안 r 마리의 개미가 이동할 수 있는지 시뮬레이션하면 된다.

 

이동할 수 있다면 정답을 mid로 기록하고,

mid 이상의 시간은 더 검사할 필요가 없으므로, right는 mid - 1로 변경한다.

 

마찬가지로 이동할 수 없다면 mid 이하의 시간은 당연히 불가능하기 때문에 더 검사할 필요가 없다. 

즉, left는 mid + 1이 된다.

	while (left <= right)
	{
		int mid = (left + right) / 2;

		... // 시뮬레이션

		if ( r 마리의 개미가 이동할 수 있다면 )
		{
			ans = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}

 

개미가 움직일 수 있는 시간 또는 거리(= mid)가 정해졌기 때문에, 이 시간에 대해 몇 마리의 개미가 필요한지 센다.

먼저 철거되지 않은 가장 첫 번째 집을 찾는다.

이 위치를 prevPos에 저장하고, start에 철거되지 않은 집의 다음 위치의 집(i + 1)의 index를 저장한다.

이 위치의 집에 개미를 한 마리 놔두기 때문에 antCount = 1이 된다.

		antCount = prevPos = 0;
		for (int i = 1; i < hcnt; i++)
		{
			if (isBroken[i] == false)
			{
				prevPos = house[i];
				start = i + 1;
				break;
			}
		}

		antCount = 1;

 

start 이상의 남은 개미집에서 철거된 집은 무시하면서 철거되지 않은 집을 찾는다.

 

그 개미집의 위치와 이전의 위치 prevPos가 mid보다 작다면

아직 개미가 움직일 수 있는 거리므로 continue로 넘어간다.

 

그렇지 않다면 개미는 mid보다 더 많은 거리를 걸어야 하므로 추가로 개미가 더 필요하다.

따라서 해당 위치를 prevPos로 갱신하고 개미의 수를 증가시킨다.

		for (int i = start; i < hcnt; i++)
		{
			if (isBroken[i] == true) continue;

			int curPos = house[i];

			if (curPos - prevPos <= mid) continue;

			prevPos = curPos;
			antCount++;
		}

 

전체 이분 탐색 코드는 다음과 같다.

int binarysearch(int r)
{
	int left, right, ans;

	left = 0;
	right = INF;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		int antCount, start, prevPos;

		antCount = prevPos = 0;
		for (int i = 1; i < hcnt; i++)
		{
			if (isBroken[i] == false)
			{
				prevPos = house[i];
				start = i + 1;
				break;
			}
		}

		antCount = 1;

		for (int i = start; i < hcnt; i++)
		{
			if (isBroken[i] == true) continue;

			int curPos = house[i];

			if (curPos - prevPos <= mid) continue;

			prevPos = curPos;
			antCount++;
		}

		if (antCount <= r)
		{
			ans = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}

	return ans;
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20000 + 10000 + 500)
#define INF (1000000000)

#define INIT (100)
#define CREATE (200)
#define REMOVE (300)
#define FIND (400)

int Q;
int N;

int house[MAX];
bool isBroken[MAX];
int hcnt = 0;

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

	hcnt = 1; // 여왕 개미의 집 house[0] = 0;
	for (int i = 0; i < N; i++)
	{
		int x;

		scanf("%d", &x);

		house[hcnt++] = x;
	}

	for (int i = 0; i < MAX; i++) isBroken[i] = false;
}

void createAntHouse(int pos)
{
	house[hcnt++] = pos;
}

void removeAntHouse(int index)
{
	isBroken[index] = true;
}

int binarysearch(int r)
{
	int left, right, ans;

	left = 0;
	right = INF;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		int antCount, start, prevPos;

		antCount = prevPos = 0;
		for (int i = 1; i < hcnt; i++)
		{
			if (isBroken[i] == false)
			{
				prevPos = house[i];
				start = i + 1;
				break;
			}
		}

		antCount = 1;

		for (int i = start; i < hcnt; i++)
		{
			if (isBroken[i] == true) continue;

			int curPos = house[i];

			if (curPos - prevPos <= mid) continue;

			prevPos = curPos;
			antCount++;
		}

		if (antCount <= r)
		{
			ans = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}

	return ans;
}

int main()
{
	scanf("%d", &Q);

	for (int q = 0; q < Q; q++)
	{
		int COMMAND;

		scanf("%d", &COMMAND);

		if (COMMAND == INIT) input();
		else if (COMMAND == CREATE)
		{
			int p;

			scanf("%d", &p);

			createAntHouse(p);
		}
		else if (COMMAND == REMOVE)
		{
			int q;

			scanf("%d", &q);

			removeAntHouse(q);
		}
		else if (COMMAND == FIND)
		{
			int r;

			scanf("%d", &r);

			printf("%d\n", binarysearch(r));
		}
	}

	return 0;
}