[코드트리] 민트 초코 우유 (삼성 SW 역량테스트 2025 상반기 오전 1번)

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

자세한 설명은 인프런 강의 미리보기에서 확인할 수 있습니다.

삼성 A형 전체 링크

참고

- BOJ 2667 : 단지번호붙이기

https://www.codetree.ai/ko/frequent-problems/problems/mint-choco-milk/description

음식은 다음과 같이 정의한다.

#define TMINT_CHOKO_MILK (111)
#define TMINT_CHOKO (1 + 10)
#define TMINT_MILK (1 + 100)
#define CHOKO_MILK (100 + 10)
#define MILK (100)
#define CHOKO (10)
#define TMINT (1)

위와 같이 음식을 정의하면, | 연산자를 이용해서 음식을 쉽게 합칠 수 있다.

예를 들어 MILK(100)와 CHOKO(10)를 | 연산하면 110이 되고, 실제 CHOKO_MILK는 100 + 10이다.

또한 같은 음식을 | 연산하면 그대로 같은 음식이 나오게 된다.

int mixFood(int sFood, int nFood)
{
	return sFood | nFood;
}

문제에서 주어진 대로 방향을 정의하고, 필요한 변수를 선언한다.

#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)

int TestCase;
int N, T;
char F[MAX][MAX];
int B[MAX][MAX];

학생의 상태를 관리하기 위해 구조체를 선언하고, 2차원 배열로 만든다.

candidates는 대표가 될 후보를 넣어두는 배열이고, group은 대표를 각각 그룹으로 나눌 때 사용한다.

struct STUDENT
{
	int food; // 신봉하는 음식
	int believe; // 신앙심
	bool isLeader; // 대표
	int defense; // 방어 여부
	int row; // 대표자 선정을 위한 값
	int col;
};

STUDENT student[MAX][MAX];
STUDENT candidates[MAX * MAX];
int ccnt;

STUDENT group[3 + 1][MAX * MAX];
int index[3 + 1];

BFS를 위해 다음과 같은 변수를 선언하였다.

struct RC
{
	int r;
	int c;
};

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

// 위, 아래, 왼쪽, 오른쪽
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };

입력은 다음과 같이 처리한다.

음식과 신앙심은 초기 입력을 받은 후, student 구조체에 다시 처리하였다.

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf(" %c", &F[r][c]);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &B[r][c]);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			student[r][c].believe = B[r][c];
			student[r][c].isLeader = false; // 초기화
			student[r][c].defense = 0; // 초기화
			student[r][c].row = r;
			student[r][c].col = c;

			if (F[r][c] == 'T') student[r][c].food = TMINT;
			else if (F[r][c] == 'C') student[r][c].food = CHOKO;
			else if (F[r][c] == 'M') student[r][c].food = MILK;
		}
	}
}

아침

모든 학생의 신앙심을 +1 증가하면 된다.

void morning()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			student[r][c].believe++;
}

점심

BFS를 이용해 방문한 곳을 제외하고, 같은 음식을 신봉하는 그룹을 찾는다.

그리고 그룹 내에서 리더를 마킹하면 된다.

BFS 실행 전에 visit과 isLeader를 초기화하였다.

void lunch()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			visit[r][c] = student[r][c].isLeader = false;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (visit[r][c] == true) continue;

			BFS(r, c);
		}
	}
}

단지번호붙이기를 응용하여 그룹을 만들면 된다.

학생의 food가 같은지 검사하면서 4방향 탐색을 진행한다.

같은 그룹의 학생을 candidates에 추가하였다.

void BFS(int r, int c)
{
	int rp, wp;

	rp = wp = 0;

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

	visit[r][c] = true;

	ccnt = 0;
	candidates[ccnt++] = student[r][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 (nr < 1 || nc < 1 || nr > N || nc > N) continue;
			if (visit[nr][nc] == true) continue;

			// 인접한 학생들과 신봉 음식이 완전히 같은 경우에만 그룹을 형성
			if (student[out.r][out.c].food != student[nr][nc].food) continue;

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

			visit[nr][nc] = true;

			candidates[ccnt++] = student[nr][nc];
		}
	}


	...
}

BFS 종료 후, candidates에서 가장 우선순위가 높은 학생을 leader로 만들고,

문제에서 요구한대로 값을 갱신하면 된다.

	STUDENT leader = { 0 };
	for (int i = 0; i < ccnt; i++)
		if (isPriority(candidates[i], leader) == true)
			leader = candidates[i];

	student[leader.row][leader.col].isLeader = true;
	student[leader.row][leader.col].believe += (ccnt - 1);

	for (int i = 0; i < ccnt; i++)
	{
		STUDENT c = candidates[i];

		if (c.row == leader.row && c.col == leader.col) continue;

		student[c.row][c.col].believe--;
	}

문제에서 요구한 우선순위는 다음과 같다.

// a가 우선순위가 더 높으면 true
bool isPriority(STUDENT a, STUDENT b)
{
	if (a.believe != b.believe) return a.believe > b.believe;
	if (a.row != b.row) return a.row < b.row;

	return a.col < b.col;
}

저녁

방어 상태와 그룹을 초기화한다.

	int defense[MAX][MAX] = { 0 };

	for (int g = 1; g <= 3; g++) index[g] = 0;

리더인 학생을 찾고, 해당 학생의 음식을 보고 그룹을 나눈다.

	// 그룹 별 분리
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			STUDENT s = student[r][c];

			if (s.isLeader == false) continue;

			int groupNumber = getGroupNumber(s.food);

			group[groupNumber][index[groupNumber]++] = s;
		}
	}

민트 초코 우유인 경우는 3번 그룹, 민트 / 초코 / 우유인 경우는 1번 그룹,

그 외에는 2번 그룹이 되도록 getGroupNumber를 구현하면 된다.

int getGroupNumber(int food)
{
	if (food == TMINT_CHOKO_MILK) return 3;
	if (food == TMINT || food == CHOKO || food == MILK) return 1;

	return 2;
}

이제 위에서 만든 isPriority를 이용해서 그룹 내 정렬을 하면 된다.

	// 그룹 내 정렬
	for (int g = 1; g <= 3; g++)
	{
		int gIndex = index[g];
		for (int i = 0; i < gIndex - 1; i++)
		{
			for (int k = i + 1; k < gIndex; k++)
			{
				STUDENT a = group[g][i];
				STUDENT b = group[g][k];

				if (isPriority(a, b) == false)
				{
					group[g][i] = b;
					group[g][k] = a;
				}
			}
		}
	}

그룹 별로 전파를 시작한다.

1. 전파자가 방어 상태인 경우는 넘어간다.

2. 전파자로 선정된 학생의 신앙심을 1로 변경한다.

3. 간절함과 방향을 계산하여 이동한다.

4. 격자 밖이거나 간절함이 0이면 전파를 종료한다.

5. 전파 대상을 찾은 경우, 음식이 서로 같거나 방어 상태면 다음 칸으로 넘어간다.

6. 음식이 다른 경우라면 전파를 시도한다. (defense 처리)

7. 문제의 조건에 따라 강한 전파 / 약한 전파 성공을 구현하였다.

8. 마지막에 defense를 초기화한다.

	// 전파 시작
	for (int g = 1; g <= 3; g++)
	{
		int gIndex = index[g];
		for (int i = 0; i < gIndex; i++)
		{
			int gr, gc;

			gr = group[g][i].row;
			gc = group[g][i].col;

			STUDENT spreader = student[gr][gc];

			// 방어 상태에서는 대표자가 되어도 전파를 하지 않음.
			if (spreader.defense != 0) continue;

			int sr, sc;

			sr = spreader.row;
			sc = spreader.col;

			// 원본의 신앙심을 1로 변경
			student[sr][sc].believe = 1;

			int x = spreader.believe - 1; // 간절함
			int dir = spreader.believe % 4;

			while (1)
			{
				int nr, nc;

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

				// 격자 밖으로 나가거나 간절함이 0이 되면 전파 종료
				if (nr < 1 || nc < 1 || nr > N || nc > N || x == 0) break;

				// 전파 대상
				STUDENT next = student[nr][nc];

				// 전파 대상이 전파자와 신봉 음식이 완전히 같은 경우
				if (next.food == spreader.food)
				{
					// 전파를 하지 않고 바로 다음으로 진행
					sr = nr;
					sc = nc;

					continue;
				}

				// 전파 대상이 전파자와 신봉 음식이 다른 경우, 전파 시도
				int y = next.believe; // 신앙심

				// 대표자에게 전파가 시도된 학생은 방어 상태
				student[next.row][next.col].defense = 1;

				if (x > y) // 강한 전파 성공
				{
					x -= (y + 1);
					if (x < 0) x = 0;

					student[next.row][next.col].believe++;
					student[next.row][next.col].food = spreader.food;
				}
				else // x <= y, 약한 전파 성공
				{
					student[next.row][next.col].believe += x;
					student[next.row][next.col].food = mixFood(spreader.food, next.food);

					x = 0;

					break;
				}

				sr = nr;
				sc = nc;
			}
		}
	}

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			student[r][c].defense = 0;

정답 출력

각 음식의 번호를 index로 활용하여 sum 배열에 신앙심을 누적하였다.

outputText 배열에서 음식들의 번호를 순서대로 저장하여 출력하면 된다.

void printAnswer()
{
	int sum[TMINT_CHOKO_MILK + 1] = { 0 };

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum[student[r][c].food] += student[r][c].believe;

	int outputIndex[7]
		= { TMINT_CHOKO_MILK, TMINT_CHOKO, TMINT_MILK, CHOKO_MILK, MILK, CHOKO, TMINT };

	for (int i = 0; i < 7; i++)
		printf("%d ", sum[outputIndex[i]]);
	putchar('\n');
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (50 + 5)

#define TMINT_CHOKO_MILK (111)
#define TMINT_CHOKO (1 + 10)
#define TMINT_MILK (1 + 100)
#define CHOKO_MILK (100 + 10)
#define MILK (100)
#define CHOKO (10)
#define TMINT (1)

#define UP (0)
#define DOWN (1)
#define LEFT (2)
#define RIGHT (3)

int TestCase;
int N, T;
char F[MAX][MAX];
int B[MAX][MAX];

struct STUDENT
{
	int food; // 신봉하는 음식
	int believe; // 신앙심
	bool isLeader; // 대표
	int defense; // 방어 여부
	int row; // 대표자 선정을 위한 값
	int col;
};

STUDENT student[MAX][MAX];
STUDENT candidates[MAX * MAX];
int ccnt;

STUDENT group[3 + 1][MAX * MAX];
int index[3 + 1];

struct RC
{
	int r;
	int c;
};

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

// 위, 아래, 왼쪽, 오른쪽
int dr[4] = { -1, 1, 0, 0 };
int dc[4] = { 0, 0, -1, 1 };

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

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf(" %c", &F[r][c]);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			scanf("%d", &B[r][c]);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			student[r][c].believe = B[r][c];
			student[r][c].isLeader = false; // 초기화
			student[r][c].defense = 0; // 초기화
			student[r][c].row = r;
			student[r][c].col = c;

			if (F[r][c] == 'T') student[r][c].food = TMINT;
			else if (F[r][c] == 'C') student[r][c].food = CHOKO;
			else if (F[r][c] == 'M') student[r][c].food = MILK;
		}
	}
}

void printBelieve() // for debug
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			printf("%d ", student[r][c].believe);
		}
		putchar('\n');
	}
	putchar('\n');
}

void printFood() // for debug
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			printf("%3d ", student[r][c].food);
		}
		putchar('\n');
	}
	putchar('\n');
}

void printGroup() // for debug
{
	for (int g = 1; g <= 3; g++)
	{
		int gIndex = index[g];
		printf("group %d ", g);

		for (int i = 0; i < gIndex; i++)
			printf("(%d, %d) ", group[g][i].row, group[g][i].col);

		putchar('\n');
	}
}

void morning()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			student[r][c].believe++;
}

// a가 우선순위가 더 높으면 true
bool isPriority(STUDENT a, STUDENT b)
{
	if (a.believe != b.believe) return a.believe > b.believe;
	if (a.row != b.row) return a.row < b.row;

	return a.col < b.col;
}

void BFS(int r, int c)
{
	int rp, wp;

	rp = wp = 0;

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

	visit[r][c] = true;

	ccnt = 0;
	candidates[ccnt++] = student[r][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 (nr < 1 || nc < 1 || nr > N || nc > N) continue;
			if (visit[nr][nc] == true) continue;

			// 인접한 학생들과 신봉 음식이 완전히 같은 경우에만 그룹을 형성
			if (student[out.r][out.c].food != student[nr][nc].food) continue;

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

			visit[nr][nc] = true;

			candidates[ccnt++] = student[nr][nc];
		}
	}

	STUDENT leader = { 0 };
	for (int i = 0; i < ccnt; i++)
		if (isPriority(candidates[i], leader) == true)
			leader = candidates[i];

	student[leader.row][leader.col].isLeader = true;
	student[leader.row][leader.col].believe += (ccnt - 1);

	for (int i = 0; i < ccnt; i++)
	{
		STUDENT c = candidates[i];

		if (c.row == leader.row && c.col == leader.col) continue;

		student[c.row][c.col].believe--;
	}
}

void lunch()
{
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			visit[r][c] = student[r][c].isLeader = false;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (visit[r][c] == true) continue;

			BFS(r, c);
		}
	}
}

int getGroupNumber(int food)
{
	if (food == TMINT_CHOKO_MILK) return 3;
	if (food == TMINT || food == CHOKO || food == MILK) return 1;

	return 2;
}

int mixFood(int sFood, int nFood)
{
	return sFood | nFood;
}

void dinner()
{
	for (int g = 1; g <= 3; g++) index[g] = 0;

	// 그룹 별 분리
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			STUDENT s = student[r][c];

			if (s.isLeader == false) continue;

			int groupNumber = getGroupNumber(s.food);

			group[groupNumber][index[groupNumber]++] = s;
		}
	}

	// 그룹 내 정렬
	for (int g = 1; g <= 3; g++)
	{
		int gIndex = index[g];
		for (int i = 0; i < gIndex - 1; i++)
		{
			for (int k = i + 1; k < gIndex; k++)
			{
				STUDENT a = group[g][i];
				STUDENT b = group[g][k];

				if (isPriority(a, b) == false)
				{
					group[g][i] = b;
					group[g][k] = a;
				}
			}
		}
	}

	// printGroup();

	// 전파 시작
	for (int g = 1; g <= 3; g++)
	{
		int gIndex = index[g];
		for (int i = 0; i < gIndex; i++)
		{
			int gr, gc;

			gr = group[g][i].row;
			gc = group[g][i].col;

			STUDENT spreader = student[gr][gc];

			// 방어 상태에서는 대표자가 되어도 전파를 하지 않음.
			if (spreader.defense != 0) continue;

			int sr, sc;

			sr = spreader.row;
			sc = spreader.col;

			// 원본의 신앙심을 1로 변경
			student[sr][sc].believe = 1;

			int x = spreader.believe - 1; // 간절함
			int dir = spreader.believe % 4;

			while (1)
			{
				int nr, nc;

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

				// 격자 밖으로 나가거나 간절함이 0이 되면 전파 종료
				if (nr < 1 || nc < 1 || nr > N || nc > N || x == 0) break;

				// 전파 대상
				STUDENT next = student[nr][nc];

				// 전파 대상이 전파자와 신봉 음식이 완전히 같은 경우
				if (next.food == spreader.food)
				{
					// 전파를 하지 않고 바로 다음으로 진행
					sr = nr;
					sc = nc;

					continue;
				}

				// 전파 대상이 전파자와 신봉 음식이 다른 경우, 전파 시도
				int y = next.believe; // 신앙심

				// 대표자에게 전파가 시도된 학생은 방어 상태
				student[next.row][next.col].defense = 1;

				if (x > y) // 강한 전파 성공
				{
					x -= (y + 1);
					if (x < 0) x = 0;

					student[next.row][next.col].believe++;
					student[next.row][next.col].food = spreader.food;
				}
				else // x <= y, 약한 전파 성공
				{
					student[next.row][next.col].believe += x;
					student[next.row][next.col].food = mixFood(spreader.food, next.food);

					x = 0;

					break;
				}

				sr = nr;
				sc = nc;
			}
		}
	}

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

void printAnswer()
{
	int sum[TMINT_CHOKO_MILK + 1] = { 0 };

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum[student[r][c].food] += student[r][c].believe;

	int outputIndex[7]
		= { TMINT_CHOKO_MILK, TMINT_CHOKO, TMINT_MILK, CHOKO_MILK, MILK, CHOKO, TMINT };

	for (int i = 0; i < 7; i++)
		printf("%d ", sum[outputIndex[i]]);
	putchar('\n');
}

void simulate()
{
	for (int t = 0; t < T; t++)
	{
		morning();
		lunch();
		dinner();

		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				if (student[r][c].defense != 0) student[r][c].defense--;

		printAnswer();
	}
}

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

		simulate();
	}

	return 0;
}

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

[코드트리] 미생물 연구 (삼성 SW 역량테스트 2025 상반기 오후 1번) (0)	2025.04.19
[코드트리] 코드트리 등산 게임 (삼성 SW 역량테스트 2024 하반기 오후 2번, B형) (2)	2024.12.20
[코드트리] 메두사와 전사들 (삼성 SW 역량테스트 2024 하반기 오후 1번) (0)	2024.12.20
[코드트리] 코드트리 DB (삼성 SW 역량테스트 2024 하반기 오전 2번, B형) (0)	2024.12.20
[코드트리] 미지의 공간 탈출 (삼성 SW 역량테스트 2024 하반기 오전 1번) (1)	2024.10.17

피로물든딸기의 라이브러리

[코드트리] 민트 초코 우유 (삼성 SW 역량테스트 2025 상반기 오전 1번)

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

자세한 설명은 인프런 강의 미리보기에서 확인할 수 있습니다.

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

댓글

티스토리툴바

[코드트리] 민트 초코 우유 (삼성 SW 역량테스트 2025 상반기 오전 1번)

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

자세한 설명은 인프런 강의 미리보기에서 확인할 수 있습니다.

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

관련글

댓글

티스토리툴바