스택/큐/우선순위큐

 

자료구조 큐의 특징을 활용한 실습 문제를 풀었다. 

벡터를 스택처럼 사용해서 진행했다. 

 

문제 1) 

 N명의 마을사람이 있다. 마을에는 사람과 외계인이 섞여있다.

사람은 진실만을 말하지만 외계인은 거짓말을 할수 도 있다.

마을 사람들은 각자 자기가 사람이라고 생각하는 사람들을 지목한다. 

첫번째 줄에 마을사람의 수를 입력받고 , 둘째 줄 부터는 I번째 사람이 M명을 지목하고 지목당한 사람들을 말한다. 

 

//마을 1
30
1 2 14 13
2 8 1 7 19 15 4 5 10 12
3 2 1 2
4 6 30 27 20 9 8 7
5 10 11 12 13 14 15 16 17 18 19 20
6 5 5 4 3 2 1
7 7 1 13 14 20 29 8 11
8 5 11 29 17 14 20
9 5 19 16 17 13 14
10 4 29 20 19 17
11 4 20 8 29 19
12 10 1 2 3 4 5 6 7 8 9 10
13 5 1 14 17 29 19
14 5 20 8 17 13 1
15 13 1 3 5 7 9 11 30 29 28 25 24 23 10
16 8 1 9 7 3 21 28 22 25
17 4 14 13 8 29
18 6 4 2 8 6 11 19
19 3 13 11 29
20 3 11 8 14
21 8 1 2 3 4 5 6 7 8
22 3 17 19 21
23 12 2 4 6 8 12 13 18 16 24 26 28 29
24 6 4 14 24 6 16 26
25 3 7 8 9
26 8 25 29 27 24 21 19 12 4
27 5 1 9 5 22 24
28 4 14 13 8 29
29 5 13 19 17 8 11
30 20 1 2 3 4 5 6 7 8 9 10 29 28 27 26 25 24 23 22 21 20

 

마을2는 1~6만명의 마을사람이 존재할때.

 

진짜 사람 판별 규칙

• ID가 1인 사람은 확정적으로 사람으로 간주.
• 이후, 이 사람이 사람이라고 증언한 사람들을 모두 사람으로 간주하며, 이를 반복(BFS 방식).

사람인지 확인하기 위해 정보(인덱스, 지목한 사람들, 사람인지 여부)  를 구조체에 담았다. 

typedef struct tagHumanInfo
{
	int id;
	vector<int> vecAnswer;
	bool isHuman;

	tagHumanInfo() : id(0), isHuman(false) {}
} HumanInfo ;

 

사람인지 확인할 함수, 전체 마을사람중 진짜 인구수를 출력하는 함수가 필요하다. 

void CheckHuman(vector<HumanInfo>& vecHumanInfo)
{
	vector<HumanInfo*> vecQueue;
	vecQueue.push_back(&vecHumanInfo[0]);	// enqueue

	for (HumanInfo* info : vecQueue)
	{
		cout << info->id << ", ";
	}
	cout << endl;

	while (vecQueue.empty() == false)
	{
		HumanInfo* front = vecQueue.front();
		vecQueue.erase(vecQueue.begin());		// dequeue

		for (int i = 0; i < front->vecAnswer.size(); i++)
		{
			int answer = front->vecAnswer[i];
			if (vecHumanInfo[answer - 1].isHuman == true)
				continue;

			vecHumanInfo[answer - 1].isHuman = true;
			vecQueue.push_back(&vecHumanInfo[answer - 1]);	// enqueue
		}
	}
}

 

• ID 1번 사람부터 시작해서, 증언 대상들을 큐에 넣으며 순차적으로 탐색
• 이미 사람으로 판단된 경우는 중복 탐색하지 않음

 

void PrintRealHumanCount(const vector<HumanInfo>& vecHumanInfo)
{
	int count = 0;

	for (auto info : vecHumanInfo)
	{
		if (info.isHuman == true)
		{
			count++;
		}
	}
	cout << "진짜 사람 수 : " << count << endl;
}

isHuman이 true인 사람의 수를 세서 출력

int main()
{
	FILE* fp = nullptr;
	fopen_s(&fp, "마을1.txt", "r");

	if (fp == nullptr)
	{
		cout << "파일을 열 수 없습니다." << endl;
		return 1;
	}

	int totalCount = 0;
	fscanf_s(fp, "%d", &totalCount);

	vector<HumanInfo> vecHuman(totalCount);

	while (1)
	{
		if (feof(fp))
			break;

		int id = 0, answerCount = 0;
		fscanf_s(fp, "%d", &id);

		if (id == 0)	break;

		vecHuman[id - 1].id = id;
		if (id == 1)
		{
			vecHuman[id - 1].isHuman = true;
		}

		fscanf_s(fp, "%d", &answerCount);
		vecHuman[id - 1].vecAnswer.resize(answerCount);

		for (int i = 0; i < answerCount; i++)
		{
			int answer = 0;
			fscanf_s(fp, "%d", &answer);
			vecHuman[id - 1].vecAnswer[i] = answer;
		}
	}

	// 사람을 확인하는 로직
	CheckHuman(vecHuman);
	// 전체 마을 인구 중 진짜 사람 수 출력
	PrintRealHumanCount(vecHuman);

	fclose(fp);
}

 

isHuman 값이 true인 사람의 수를 세서 출력한다. 

 

첫번째 사람은 무조건 사람이므로 id == 0인 경우에 예외처리를 해줬다. 

 

수업시간에는 std::queue를 쓰지않고 벡터를 큐처럼 써서 erase시 시간복잡도가 O(N)이다. 

큐를 쓰면 O(1)로 개선할 수 있다.

 

void CheckHuman(vector<HumanInfo>& vecHumanInfo)
{
    queue<HumanInfo*> q;
    q.push(&vecHumanInfo[0]);

    while (!q.empty())
    {
        HumanInfo* front = q.front();
        q.pop();

        for (int answer : front->vecAnswer)
        {
            HumanInfo& target = vecHumanInfo[answer - 1];
            if (target.isHuman) continue;

            target.isHuman = true;
            q.push(&target);
        }
    }
}

 

스택은 나중에 들어온게 먼저 나가고 뒤에서만 삽입/삭제가 가능한 자료구조이다. DFS나 재귀처리에 사용된다. 

큐의 특징은 선입선출, 먼저들어온것이 먼저 나가는 것이다. 삽입/삭제 위치가 다르다. 

덱(DoubleEnded queue)는 큐와 다르게 양방향 삽입/삭제가 가능한게 특징이다.

특히 우선순위 큐는  BFS탐색, 다익스트라 알고리즘이나 작업스케쥴링에  사용된다. 

 

🧱 1. 스택 (Stack)

📌 특징: LIFO (Last In, First Out)

🎮 게임에서의 사용 예

Undo/Redo 시스템	예: 카드 게임, 턴제 게임에서 행동 되돌리기
씬 전환	예: 메뉴 → 옵션 → 설정 → 뒤로가기
스킬 처리 순서	예: 도트 피해 효과 순차적 해제
상태 변화 관리	예: 버프/디버프 순차 적용 및 해제

 

🔃 2. 큐 (Queue)

📌 특징: FIFO (First In, First Out)

🎮 게임에서의 사용 예

사용 예시설명

이벤트 큐	예: 몬스터가 죽은 뒤 처리할 효과/상태 등
턴 관리	예: 카드 게임, 보드 게임
AI 명령 큐	예: NPC가 순차적으로 행동 수행
네트워크 패킷 처리	순차적으로 처리 필요

 

↔️ 3. 덱 (Deque)

📌 특징: 양쪽 삽입/삭제 가능

🎮 게임에서의 사용 예

턴 기반 전략 게임	캐릭터 우선순위에 따라 앞/뒤에서 삽입
슬라이딩 윈도우 처리	예: 유닛 스캔 범위 계산
입력 버퍼 처리	예: 격투 게임에서 커맨드 입력 순서 처리
AI 행동 우선순위 조정	상황에 따라 앞 or 뒤에서 삽입

 

🔺 4. 우선순위 큐 (Priority Queue)

📌 특징: 높은 우선순위부터 꺼냄 (기본은 최댓값 기준)

🎮 게임에서의 사용 예

AI 행동 우선순위	예: 체력 낮은 적 → 회복 먼저, 가까운 적 → 공격
스킬 발동 대기열	쿨타임 짧은 스킬부터 발동
경로 탐색 (다익스트라)	A* 알고리즘에서 사용
이벤트 처리 우선순위	치명적 상황 우선 처리