[코드트리] 택배 하차 (삼성 SW 역량테스트 2025 하반기 오전 1번)

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

 

삼성 A형 전체 링크

 

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/delivery-service/description

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

 

택배 상자는 다음과 같이 정의한다.

(r, c)는 상자의 가장 위, 왼쪽의 좌표이며, 배달 완료된 상자는 drop으로 체크한다.

struct BOX
{
	int k;
	int h;
	int w;
	int r;
	int c;
	bool drop;
};

BOX box[100 + 10];

 

가장 큰 상자의 번호가 M이라는 보장이 없으므로 maxBoxNum을 따로 관리한다.

input에서 0으로 초기화하고, 모든 box의 k도 0으로 초기화한다.

MAP의 바깥 좌표는 -1로 처리한다.

void input()
{
	maxBoxNum = 0;

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= 100; i++)
		box[i].k = 0;

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

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

---

시뮬레이션을 위해 다음의 함수를 정의한다

 

setBox(index) - 상자를 MAP에 적어둔다.

deleteBox(index) - 상자를 MAP에서 삭제한다.

checkDown(index) - 상자가 아래로 내려갈 수 있는지 체크한다.

moveDown(index) - 상자 하나를 내릴 수 있을 때까지 내린다.

moveDownAll() - 모든 상자를 내릴 수 있을 때 까지 내린다.

checkLeft(index) - 왼쪽으로 상자를 하차할 수 있는지 확인한다.

moveLeft() - 왼쪽으로 상자를 하차하고 상자 번호를 출력한다.

checkRight(index) - 오른쪽으로 상자를 하차할 수 있는지 확인한다.

moveRight() - 오른쪽으로 상자를 하차하고 상자 번호를 출력한다.

 

위의 함수가 모두 갖추어졌다면, 아래의 시뮬레이션으로 택배 하차 문제를 해결할 수 있다.

 

1. 택배를 M개 투입한다. (박스의 번호와 M은 무관함에 주의)

2. 좌측 / 우측 번갈아서 M / 2번 택배를 하차한다. (M이 홀수라면 마지막 moveRight는 아무 행동도 하지 않는다.)

 

모든 택배가 MAP에 투입이 완료되는 것을 보장하므로, box의 r을 1로 초기화하고 상자를 투입하였다.

void simulate()
{
	// 1. 택배 투입
	for (int m = 0; m < M; m++)
	{
		int k, h, w, c;

		scanf("%d %d %d %d", &k, &h, &w, &c);

		box[k].k = k; // m과 k가 다를 수 있음.
		box[k].h = h;
		box[k].w = w;
		box[k].r = 1;
		box[k].c = c;
		box[k].drop = false;

		if (maxBoxNum < k) maxBoxNum = k;

		moveDown(k);
	}

	for (int m = 0; m < M; m += 2)
	{
		// 2. 택배 하차 (좌측)
		moveLeft();
		moveDownAll();
		
		// 3. 택배 하차 (우측)
		moveRight();
		moveDownAll();		
	}
}

---

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50 + 5)

int T;
int N, M, maxBoxNum;

int MAP[MAX][MAX];

struct BOX
{
	int k;
	int h;
	int w;
	int r;
	int c;
	bool drop;
};

BOX box[100 + 10];

void input()
{
	maxBoxNum = 0;

	scanf("%d %d", &N, &M);

	for (int i = 1; i <= 100; i++)
		box[i].k = 0;

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

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

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

void setBox(int index)
{
	BOX b = box[index];

	for (int r = b.r; r < b.r + b.h; r++)
		for (int c = b.c; c < b.c + b.w; c++)
			MAP[r][c] = index;
}

void deleteBox(int index)
{
	BOX b = box[index];

	for (int r = b.r; r < b.r + b.h; r++)
		for (int c = b.c; c < b.c + b.w; c++)
			MAP[r][c] = 0;
}

bool checkDown(int index)
{
	BOX b = box[index];

	bool check = false;
	for (int c = b.c; c < b.c + b.w; c++)
	{
		if (MAP[b.r + b.h][c] != 0)
			return false; // 이동 불가
	}

	return true;
}

void moveDown(int index)
{
	BOX b = box[index];

	deleteBox(index);

	while (1)
	{
		if (checkDown(index) == false) break;

		b.r += 1; // 임시값 수정
		box[index].r += 1; // 실제값 수정
	}

	setBox(index);
}

void moveDownAll()
{
	while (1)
	{
		bool check = true;
		for (int i = 1; i <= maxBoxNum; i++)
		{
			if (box[i].drop == true || box[i].k == 0) continue;
			if (checkDown(i) == false) continue;

			check = false;

			moveDown(i);
		}

		if (check == true) break;
	}
}

bool checkLeft(int index)
{
	BOX b = box[index];
	for (int r = b.r; r < b.r + b.h; r++)
		for (int c = 1; c < b.c; c++)
			if (MAP[r][c] != 0) return false;

	return true;
}

void moveLeft()
{
	for (int i = 1; i <= maxBoxNum; i++)
	{
		if (box[i].drop == true || box[i].k == 0) continue;

		if (checkLeft(i))
		{
			box[i].drop = true;
			deleteBox(i);

			printf("%d\n", i);
			return;
		}
	}
}

bool checkRight(int index)
{
	BOX b = box[index];
	for (int r = b.r; r < b.r + b.h; r++)
		for (int c = b.c + b.w; c <= N; c++)
			if (MAP[r][c] != 0) return false;

	return true;
}

void moveRight()
{
	for (int i = 1; i <= maxBoxNum; i++)
	{
		if (box[i].drop == true || box[i].k == 0) continue;

		if (checkRight(i))
		{
			box[i].drop = true;
			deleteBox(i);

			printf("%d\n", i);
			return;
		}
	}
}

void simulate()
{
	// 1. 택배 투입
	for (int m = 0; m < M; m++)
	{
		int k, h, w, c;

		scanf("%d %d %d %d", &k, &h, &w, &c);

		box[k].k = k; // m과 k가 다를 수 있음.
		box[k].h = h;
		box[k].w = w;
		box[k].r = 1;
		box[k].c = c;
		box[k].drop = false;

		if (maxBoxNum < k) maxBoxNum = k;

		moveDown(k);
	}

	for (int m = 0; m < M; m += 2)
	{
		// 2. 택배 하차 (좌측)
		moveLeft();
		moveDownAll();
		
		// 3. 택배 하차 (우측)
		moveRight();
		moveDownAll();		
	}
}

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

		simulate();		
	}

	return 0;
}