우리 게임엔 유물이라는 요소가 있다. 유물은 던전 탐사 혹은 전투 중 팀 전체에게 이득을 주는 요소로, 다양한 상황에서 다양한 효과를 일으킨다. 아래는 유물의 예시이다.

  • 유물 A: SP를 5 획득할 때마다, 적 전체에게 피해를 10 줍니다.
  • 유물 B: SP를 3 이상 소모하는 스킬의 피해량이 6 늘어납니다.
  • 유물 C: 전투 종료 시 HP가 50% 이하인 아군은 HP를 18 회복합니다.

이걸 어떻게 전투와 연결할 수 있을까? 우리의 액션 기반 전투 시스템에 이걸 연결하는 방법은 몹시 간단하다. 특정 행동을 했을 때 호출되는 함수를 준비해두고, 각 유물을 구현할 때 필요한 행동에 대해서만 그 함수를 구현하면 된다. 아래는 유물 A를 구현한 간략한 C# 코드이다.

// 반응형 함수들의 원형. 유물 뿐 아니라 여러 요소를 구현하는데 쓰인다.
public abstract class GameEventHandler {
    public virtual List<ICombatAction> OnChangeSp(CombatModel combat, int amount) => null;
    public virtual List<ICombatAction> OnSpellCast(CombatModel combat, SpellModel spell) => null;
    public virtual List<ICombatAction> OnCombatEnd(CombatModel combat) => null;
    // More functions..
}

public abstract class Relic : GameEventHandler {
    public int Counter { get; protected set; }
}

public class RelicA : Relic {
    public override List<ICombatAction> OnChangeSp(CombatModel combat, int amount) {
    	// 소모된 SP를 Relic.Counter를 이용해 저장
        Counter += amount;
        
        List<ICombatAction> derivedActions = new();
        
        // Counter가 5가 넘으면 모두에게 10 피해를 주는 액션을 생성해 반환함.
        while (Counter >= 5) {
            Counter -= 5;
            
            AllDamageAction action = new(combat.Enemies, 10);
            
            derivedActions.Add(action);
        }
        
        return derivedActions;
    }
}

 

구조가 어렵지 않음을 알 수 있다. 그리고 실제로 Model-side에서 SP를 변화시키는 코드가 호출될 때는 아래 코드처럼 할 수 있다.

public class CombatModel {
    public int Sp { get; private set; }
    public int MaxSp { get; private set; }
    private List<Relic> _relics;
    public IReadOnlyList<Relic> Relics => _relics;

    // Naive한 버전. 부가 효과를 Action 기반 시스템과 연결하기 어렵다.
    public void ChangeSp(int amount) {
    	Sp = Math.Clamp(Sp + amount, MaxSp);
    }
    
    // 부가 효과를 Action 기반 시스템과 올바르게 연결한 버전.
    public List<ICombatAction> ChangeSp(int amount) {
    	int beforeSp = Sp;
        Sp = Math.Clamp(Sp + amount, MaxSp);
        
        int actualAmount = Sp - beforeSp;
        
        List<ICombatAction> derivedActions = new();
        
        foreach (Relic relic in _relics) {
            List<ICombatAction> relicActions = relic.OnChangeSp(this, amount);
            derivedActions.AddRange(relicActions);
        }
        
        return derivedActions;
    }

}

 

기존에 Action 기반 시스템을 잘 갖춰놓아 구현이 매우 쉬웠다. 기술적으로 엄청 특이한 건 아니지만 잘 작동하는 걸 보니 즐겁다.

'Unity, 게임 개발' 카테고리의 다른 글

2026.05.06 (수) - 상태 이상 시스템 구현  (0) 2026.05.07
2026.02.28 (토) 턴제 애니메이션 구현하기  (0) 2026.02.28
2026.02.09 (월)  (0) 2026.02.10
2026.02.02 (월)  (1) 2026.02.03

턴제 게임에서 캐릭터가 상태 이상을 갖는 것은 비교적 흔한 일이다. 우리 게임에서도 이게 필요했기에 구현을 해 나갔다.

 

게임의 특징을 되짚어보자면,

  • 턴제이지만 속도 기반이라, 여러 캐릭터가 동등하게 차례를 하나씩 갖지 않는다. 예를 들어 속도가 빠른 캐릭터 A가 있고, 속도가 느린 캐릭터 B가 있다고 하자. A가 두 번 행동할동안 B는 한 번만 행동하게 되는 경우가 존재한다. 또한 A가 "느린" 스킬을 사용하면 속도가 빠름에도 불구하고 B와 같은 빈도로 행동하게 될 수도 있다. 즉, 캐릭터와 스킬 모두에 속도 개념이 존재하고, 시스템에는 이를 관리하기 위한 내부적인 턴 타이머가 존재한다. 이를 전투 시간이라 부르겠다.
  • 상태 이상은 캐릭터의 행동 차례가 되었을 때, 특정 행동을 했을 때, 일정 전투 시간이 지났을 때, 혹은 제거되었을 때 발동하는 등의 여러 유형이 있다. 독, 재생과 같은 지속형 효과는 일정 전투 시간마다 발동되는게 자연스럽고, [다음 피해 3번이 강화]되는 상태 이상은 특정 행동을 했을 때마다 발동되는게 자연스럽다. 이렇듯 여러 유형의 상태 이상을 구현할 수 있어야 했다.

 

캐릭터와 상태이상의 처리

우선 캐릭터는 전투 중에 턴 타이머 기반으로 작동한다.

  • 전투 중인 모든 캐릭터를 TurnManager 에 등록한다. 각 캐릭터는 다음 행동이 가능한 타이머(NextTurnTime)를 갖고, 이 타이머 순으로 정렬되어 저장된다.
  • TurnManager 는 NextTurnTime 이 가장 작은 것을 꺼내온다(Priority Queue로 구현). 각 캐릭터의 유형에 따라 어떤 작업을 할지 정하는데, 아군 캐릭터라면 무슨 행동을 할지 사용자가 선택할 수 있게 하고 적군 캐릭터라면 게임이 알아서 골라준다. 이 작업을 행동 차례 처리라 부르자. TurnManager는 전투가 끝났다고 판단될 때까지 행동 차례 처리를 반복한다.

여기서 각 상태 이상 유형을 어떻게 처리할 수 있을지 생각해보자.

  • 행동 차례가 되었을 때, 특정 행동을 했을 때: TurnManager가 행동 차례 처리 를 하거나 특정 행동이 된 시점에 상태 이상에 등록된 함수를 실행한다. 예를 들면 다음 코드와 같을 것이다. 굉장히 쉽다.
public void ProcessEntityAction(EntityModel entity) 
{
    foreach (StatusEffectModel ste in entity.StatusEffects) 
    {
    	ste.OnActionStart();
    }
}
  • 일정 전투 시간이 지났을 때 / 일정 전투 시간마다 발동: 약간 까다로울 수 있는 케이스지만 그냥 TurnManager에 넣는 요소로 생각하면 쉽다.
    캐릭터는 NextTurnTime으로 다음에 행동할 시점을 정할 수 있다. 그렇다면 상태 이상을 캐릭터처럼 취급하고 속도를 부여한다면, 일정 전투 시간마다 작동하는 것을 아주아주 쉽게 구현할 수 있다. 상태 이상과 캐릭터를 CombatElement라는 상위 class로 묶어 TurnManager에 관리하게 시키면 매우 쉬워진다.
    상태 이상은 지속 시간을 가지는 것도 있을 수 있으므로 지속 시간 확인도 필요하다. 이는 Expired 라는 flag를 두어 확인할 수 있다. 지속 시간이 다 되었거나 강제로 제거되었다는 등의 이유로 만료 처리된 상태 이상은 TurnManager가 별도로 처리한다.
public void ProcessElementAction(CombatElement element) 
{
    switch (element) 
    {
    	case EntityCombatElement entity: 
        {
            foreach (StatusEffectModel ste in entity.StatusEffects) 
            {
            	ste.OnActionStart();
            }
            break;
        }
        case StatusEffectCombatElement steElement: 
        {
            if (steElement.Expired) return;
            steElement.OnPeriod();
            break;
        }
    }
}
  • 제거되었을 때: TurnManager가 지속 시간이 다 되었거나 강제로 제거되는 등의 이유로 만료된 상태 이상을 제거할 때, 비슷한 방식으로 관련 함수들을 호출하면 된다.

 

애니메이션은 어떻게?

이전 글 에서는 애니메이션을 구현할 때, 먼저 액션이 트리를 순회하듯 처리되고 그 과정에서 애니메이션 트리가 구축되는 방식을 사용했다고 했다. 마찬가지로 상태 이상도 똑같이 해주면 된다. 상태 이상이 특정 효과(액션)를 일으키면, 연쇄적으로 파생 액션이 생성되어 처리되는 방식이다. 구조를 잘 만들어 둔 것 같아 뿌듯하다.

 

'Unity, 게임 개발' 카테고리의 다른 글

2026.05.13 (수) - 유물과 전투 연결 구현  (0) 2026.05.14
2026.02.28 (토) 턴제 애니메이션 구현하기  (0) 2026.02.28
2026.02.09 (월)  (0) 2026.02.10
2026.02.02 (월)  (1) 2026.02.03

~2026.02.28 (토)

 

매일 글을 쓴다고 해놓고 거의 글을 안 썼다. 글을 쓴다고 마음먹는 것부터 쉽지 않게 느껴지지만 그래도 열심히 써야겠지..

 

2월 9일 이후로 약 2 ~ 3주간 고민한 내용은 애니메이션이었다. 어떤 종류의 애니메이션이든 게임 개발에선 빼놓을 수 없기에 애니메이션의 구현을 잘 정립하는 것은 아주 중요했다.

친구에게 들어보니 Unity에서 애니메이션을 자체적으로 지원한다고 한다. 하지만, 그 시스템은 턴제에는 적합하지 않다고도 말해주었다. 우리는 액션을 처리하면 액션에 달려있는 애니메이션을 재생하는 방식으로 게임을 굴러가게 하고 싶었다. 액션을 처리하면 새로운 액션이 생성되고, 그 액션의 애니메이션도 정해진 순서와 시점에 따라 재생하는 방식으로.


액션 시스템

 

액션 시스템을 가볍게 예시와 함께 설명하면 이렇다. 플레이어가 스킬을 사용하면 코드는 SpellCastAction이라는 액션을 받아 처리한다. SpellCastAction을 처리하면, AttackDamageAction과 StatusEffectAction 등의 파생 액션이 생겨난다. 이 파생 액션들도 각각의 애니메이션을 갖고 있다.

이런 방식을 택한 이유는 우리가 레퍼런스로 삼은 게임인 Slay the Spire가 이러한 방식을 채택하고 있고, 우리 게임도 비슷하게 굴러가기 때문이다. 만약 플레이어가 아이템, 유물 등의 부가 효과를 주는 물건들을 보유하고 있다면 더 많은 파생 액션들이 생성된다.

그러나 각각의 액션에 대한 애니메이션을 처리하는 것은 조금 어려울 수 있다. 몇몇 애니메이션은 다른 애니메이션과 동시에 실행하고 싶고, 몇몇 애니메이션은 다른 애니메이션과 순차적으로 실행하고 싶다. 다음 예시를 생각해보자.

 

[스킬을 시전해서, 상대에게 피해를 8 주고 유물 효과로 피해를 3 더 주는 상황]

 

여기엔 다음과 같은 애니메이션이 들어간다.

[스킬 시전 동작 애니메이션]

[피해를 8 주는 애니메이션]

[유물을 강조하는 애니메이션]

[피해를 3 주는 애니메이션]

 

이 애니메이션들을 단순하게 순차적/병렬적으로 실행하면 이상하게 보일 수 있다. 최소한 3번째, 4번째 애니메이션은 동시에 실행하고 싶다. 유물 효과로 피해를 입히는 것이므로 유물을 강조하는 효과와 피해가 3 들어가는 효과를 동시에 실행하면 자연스럽기 때문이다.

또한, 스킬 시전 동작이 전부 끝난 후에야 피해가 들어가거나 유물이 강조되는 것은 어색할 수 있다. 만약 스킬 시전 동작이 [스킬 쓰러 상대에게 이동, 상대에게 검 내려침, 다시 자기 자리로 돌아옴]의 3가지의 동작으로 나뉘어 있다면 어떻겠는가? 이 3가지가 전부 끝난 다음에 피해를 8 주는 애니메이션이 재생된다면 어색할 것이다.

 

따라서, 애니메이션을 여러 파트로 나눠 생각해보기로 했다. 


애니메이션의 분리

1. DAG로 접근

 

모든 애니메이션은 여러 파트로 쪼개 생각할 수 있다. 아까 언급했던 [스킬 시전 동작 애니메이션] 같은 경우,

[스킬 쓰러 상대에게 이동 | 상대에게 검 내려침 | 다시 자기 자리로 돌아옴] 의 3가지 동작으로 나눌 수 있다. 애니메이션을 이렇게 나눌 수 있다면, 다음 애니메이션을 언제 실행할지 정할 수 있을 것이다.

[피해를 8 주는 애니메이션] 은 [상대에게 검 내려침] 파트를 실행할 때 혹은 완료됐을 때 실행하면 좋을 것이다. 이건 그래프로 모델링할 수 있겠다는 생각이 들었다. 다음과 같은 간선을 갖는 그래프를 생각해보자.

 

[상대에게 검 내려침] -> [피해를 8 주는 애니메이션]

[피해를 8 주는 애니메이션] -> [유물 강조 효과]

[피해를 8 주는 애니메이션] -> [피해를 3 주는 애니메이션]

 

이건 유향 비순환 그래프(Directed Acyclic Graph)로 표현할 수 있다. 선행되는 애니메이션 파트들이 모두 실행되었다면 이 애니메이션 파트를 실행할 수 있는 방식이다.

이론적으로 완벽하지만 이 방식은 아주 큰 문제가 있었는데, DAG를 해석하고 실행하는 것은 쉬워도 구성하는 것은 아주아주 어렵다는 점이었다.

애니메이션을 연결하려면 다른 애니메이션의 Reference를 쉽게 접근할 수 있도록 해야했고, 어떤 애니메이션들을 Parent-Child 관계로 연결해야할지 찾는 것이 정말 막막했다. 액션이 나오는 패턴이 정해져 있다면 모를까, 유물이나 장비 및 아이템 등 여러 요소들로 인해 액션이 추가되면 Parent-Child 관계를 연결하는 것은 너무나도 복잡해진다.

 

2. 트리로 접근

 

DAG를 구성하는 것이 어려워서, 더 쉬운 구조를 생각해보기로 했다. 그것은 바로 트리였다.

우리 시스템의 액션은 액션(1, 2)을 하나(1) 처리하면, 그 액션(1)의 파생 액션(1a, 1b)이 생성되어 계속 처리되는 구조였다. 1a, 1b를 모두 처리하기 전까지 2를 처리하지 않는 구조이다. 이건 트리 구조와 완전히 같기 때문에, 액션 트리로부터 애니메이션 트리를 만들어내면 어떨까 하는 생각이 들었다.

 

액션을 생성하고 처리하면, 애니메이션 트리도 생성된다. 액션과 애니메이션을 1:1로 대응시키면 Model-side 코드가 View-side 코드의 규칙을 알고 있을 필요도 없이, 액션 트리와 동일한 구조로 애니메이션 트리를 만들어 실행시키면 된다.

 

트리를 만들었다면 트리를 순회할 규칙을 정해야 한다. 규칙은 간단하게 Preorder (루트 - 왼쪽 - 오른쪽) 로 했고, 각 노드가 애니메이션의 한 파트에 대응하게 만들었다. Pseudo-code로 쓰면 다음과 같다.

public async Task Preorder() 
{
	var handle = this.Animation();
    
    foreach (var child in this.Children) {
    	await child.Preorder();
    }
    
    await handle;
}

 

이를 생각해내는 것은 꽤 오래 걸렸지만 결과물은 꽤나 마음에 들었다.

 

'Unity, 게임 개발' 카테고리의 다른 글

2026.05.13 (수) - 유물과 전투 연결 구현  (0) 2026.05.14
2026.05.06 (수) - 상태 이상 시스템 구현  (0) 2026.05.07
2026.02.09 (월)  (0) 2026.02.10
2026.02.02 (월)  (1) 2026.02.03

2026.02.03 (화) ~ 2026.02.08 (일)

 

2월 2일에 하던 작업을 마무리 지었다. 지난 주의 목표는 플레이어의 캐릭터를 조작할 수 있는 UI를 만들고, UI와의 상호작용을 통해 턴이 흘러가는 전투를 시각적으로 구현하는 것이었다.

게임의 상태를 관리하기 위해 채택했던 Stack 기반 FSM이 이때 빛을 발했다. UI의 입력에 따라 행동하는 방식이 달라지는데, Stack을 활용해 UI에서 전달한 입력의 종류를 상태마다 따로 처리하도록 해서 쉽게 구현했다.

주중에 대전을 다녀오느라 제작한 내용이 많지 않지만, 목표하던 바는 달성했다.


2026.02.09 (월)

 

이번 주의 목표는 전투 후 보상을 수령하는 UI와 그 상호작용을 구현하는 것이다. 이것까지 구현하면 던전 안에서의 흐름을 끊김 없이 구현할 수 있게 된다.

..하지만 다른게 하고 싶어져서, 보상 UI 대신에 전투 UI의 부족한 부분을 조금 더 손봤다. 마음이 가는 부분을 하는 것은 어쩔 수 없는 것 같다.

 

스킬이 사용될 지역을 보여주는 UI를 만들고 싶어서, 스킬 대상의 유형을 나타내는 record를 구현했다. Discriminated Union을 사용해서 스킬 대상 유형을 단일 / 정사각형 / 무작위 등으로 나누고 싶었는데, 이걸 구현하는데 abstract record + sealed record를 사용해 record의 계층 구조를 만들었다.

 

public abstract record SpellTargetType 
{
	private SpellTargetType {}
    public sealed record Single : SpellTargetType;
    public sealed record Square(int Range) : SpellTargetType;
}

 

그런데 이 코드는 컴파일이 되지 않았다. 놀랍게도 Unity 매뉴얼에 적혀 있는 내용이더라.. record를 Unity에서 제대로 사용하려면, IsExternalInit 타입을 특정 네임스페이스에 선언해야 한다. (https://docs.unity3d.com/6000.3/Documentation/Manual/csharp-compiler.html) 현재 Unity의 LTS 버전인 6.3 버전에선 .NET 버전이 딸려 어쩔 수 없나보다.

최근에 친구들과 같이 팀을 짜 총 3인 팀으로 게임 개발을 하고 있다. 취미 느낌으로 시작했지만, 출시하는 것도 목표로 하고 있다.

기획과 프로그래밍은 2025년 9월부터 시작했지만, 2025년 12월에 KAIST에서의 마지막 학기가 끝나고 난 뒤부터 본격적으로 프로그래밍을 하고 있다.

 

앞으로 매일 게임 개발을 하며 겪은 사소한 일들을 블로그에 적으며 정리해보려 한다. 프로그래밍을 주로 하고 있기 때문에, 프로그래밍에 관한 내용들을 적으려 한다. 기획은 어느 정도는 비밀로 해야 하지 않을까 싶어 많이 적지 않으려 한다.


만들고 싶은 게임

 

우리가 만드려는 게임은 던전에서 여러 방을 차례대로 격파하며 마지막 방까지 클리어하면 던전을 완료하는, 로그라이크 장르에서 많이 볼 수 있는 구조이다. 다만 정통 로그라이크 방식으로 게임을 만들면 진입장벽이 높아 사람들을 끌어모으기 어렵기 때문에, 우리는 허브(집)를 추가하고 허브에서 영구적 강화를 할 수 있도록 하기로 했다. 이는 요즘 나오는 로그라이 게임에서 흔한 방식이라 생각한다.

 

나는 프로그래밍으로 게임을 구현하는 작업을 주로 하고 있다. 허브, 던전, 전투가 전부 나오는 구조를 만들고 싶었기 때문에 이 세 가지를 분리하여 따로따로 작업을 했다. 원래 나는 던전 쪽만 만드는 것이었는데, 프로젝트를 진행하다 보니 나머지 부분도 같이 만들기로 했다. 아직 허브는 구현이 되어 있지 않아 우선은 던전 + 전투를 만들어서 간단하게라도 돌려보는 것이 목표이다.


2026년 2월 1일 (일)

 

2026년 2월 1일 (일)에 오프라인 회의가 3시간 정도 있었다. 라즈베리 라떼를 시켜 마시며 신나게 떠들었다.

우리가 만드는 게임은 로그라이크, 속도 기반 턴제, 다대다 전투 등의 키워드를 가진 게임이다. 이때 회의에서는 피해량 계산 시스템, 캐릭터 성장 방식, 그리고 새로운 커맨드와 게임 시스템이 지금껏 구상해온 컨셉에 맞는지 등 다양한 이야기를 했다.

 

이날 회의를 위해 늦게까지 안 자고 구현을 했었는데, 회의 날 와보니 다른 친구들도 전부 잠을 덜 자서 피곤하다고 했다. 조금 걱정되긴 했지만 막상 회의를 시작하니 다들 열심히 의견을 내며 떠들어서 만족스러웠다. 이 날은 기획 회의를 2시간 30분 정도 하고, 나머지 30분은 내가 지금까지 구현한 데모를 보여주었다.

 

데모는 속도 기반 턴제를 구현한, 디자인이라곤 하나도 없이 오직 뼈대만 있는 게임이었다. 무료 에셋으로 채운 캐릭터와 스프라이트 시트조차 추가하지 않은 적들, 대충 만든 UI... 그래도 필요한 건 다 있어서 그런지, 정말 감사하게도 팀원들이 호평해주었다. 앞으로 어떤 것을 구현할 지 이야기하고 이 날 회의는 마무리되었다.


2026년 2월 2일 (월)

 

오늘은 눈이 내려 집 앞 눈을 치우느라 늦게 작업을 시작했다. 늦게 작업을 시작하니 그만큼 게을러지는 것 같다.

 

행동 순서 표시 UI, 스킬 포인트 UI

턴제 기반 전투는 보통 행동 순서가 간단한 편이다. 내가 한 번 행동하면 상대가 한 번 행동하고, 이게 반복. 그러나 우리는 속도 기반 턴제를 구현하기로 했었다. 다대다 전투를 구현하고, 각 캐릭터에 행동 속도가 있고, 각 행동에도 고유 속도가 있는 방식.

이걸 구현하는 것은 코드 상으로는 되어 있었지만 UI는 없었기에 구현했다. 디자인은 추후에 신경쓰기로 하고 우선은 돌아가는지만 확인하기로 했다.

 

또한 스킬 포인트 UI를 만들었다. 속도 기반 턴제 뿐 아니 팀 단위 스킬 포인트를 사용하는 전투이기에 스킬 포인트를 표시할 수 있는 UI가 필요해 간단하게 구현했다. 역시나 디자인은 나중에 신경쓰기로 했다.

 

StringManager

다음으로 StringManager라는 녀석을 구현해 놓기로 했다. 여러 언어를 지원할 수 있게 확장성을 챙기려면 어떻게 해야 할까 하는 고민에서 나온 것이다. UI와 게임 화면에 보이는 문자열들은 언어마다 다를 것이므로, 이걸 C# Dictionary로 관리하면 좋겠다는 생각이 들었다. 어떤 언어를 쓸 것인가에 따라 서로 다른 문자열을 반환하면 되니까.

기존에는 코드에 문자열을 하드코딩해놓았지만 확장성이 매우 부족한 구조이므로 StreamingAssets에 json 형식으로 저장하고 불러오는 방식으로 변경하고, 그 구현을 StringManager로 하기로 했다.

 

우리 게임은 MVC 디자인 패턴을 따르고 있어, StringManager의 문자열들을 채우는 것은 Controller 단에서 하기로 했다. 하지만 언제 어떤 문자열들을 채울지는 아직 정해진 것이 없다. 어떤 유형의 문자열들이 가장 많은 비율을 차지할지는 아직 모르겠다. 유물? 스킬? 캐릭터 정보? 아무래도 스킬이지 않을까 싶기는 하지만 그래도 양을 봐야할 것이다. 또한, StringManager는 전역 변수처럼 기능하므로 메모리 사용량도 고려해야 할 것이다. 던전에 입장할 때 던전에서만 사용하는 문자열들을 불러오고, 퇴장할 땐 제거한다던지. 물론 많은 양의 string보다 Unity 스프라이트 하나가 더 많은 메모리를 잡아먹을 것 같지만, 사소한 최적화도 신경쓰고 싶다.

 

생각할게 많아지다보니 StringManager의 구현은 우선은 껍데기만 해놓고, 메서드들은 나중에 하기로 했다. 당장의 목표는 MVP를 만드는 것이라 확장성은 살짝 후순위로 두고, 문자열을 하드코딩하는 것으로 진행하고 나중에 변경하려 한다.

 

 

문제 링크: https://acmicpc.net/problem/5782 

 

5782번: This Sentence is False

The input file contains several instances of documents. Each document starts with a line containing a single integer, N, which indicates the number of sentences in the document (1 ≤ N ≤ 1000). The following N lines contain each a sentence. Sentences ar

www.acmicpc.net


문제를 요약해봅시다.

  • 주어진 $N$개의 문장은 각각 다른 문장 $X$의 참, 거짓 여부를 가리킵니다.
  • 문장의 참, 거짓 여부를 조사하여 만약 모순이면 Inconsistent를, 모순이 아니면 참이 될 수 있는 문장의 최대 개수를 출력합니다.

- 사실 관계 유추

어떤 문장 $X$의 내용이 "문장 $Y$는 참이다" 라고 합시다. 이때 유추할 수 있는 사실은 다음의 2가지입니다.

  • 문장 $X$가 참이면, 문장 $Y$도 참입니다.
  • 문장 $X$가 거짓이면, 문장 $Y$도 거짓입니다.

 

이때 이 두 명제의 역도 성립합니다. 왜냐하면, 문장 $Y$가 참이면 문장 $X$가 참을 말하고 있는 것이기 때문입니다! 문장 $Y$가 거짓인 경우도 비슷합니다.

이와 유사하게, 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 인 경우도 생각해 볼 수 있습니다. 이때 유추할 수 있는 사실은,

  • 문장 $X$가 참이면, 문장 $Y$는 거짓입니다.
  • 문장 $X$가 거짓이면, 문장 $Y$는 참입니다.

이 두 명제의 역도 역시나 성립합니다.

 

- 문제 구성 (그래프)

이러한 문장 간의 사실 관계를 나타낼만한 좋은 자료구조가 없을까요? 바로 그래프입니다.

그래프를 이용해서 문장 간의 관계를 표현해봅시다.

  • 문장 $X$가 참인 경우와 거짓인 경우를 각각 정점 $x$, $\neg x$로 쓰겠습니다.
  • 문장 $X$의 내용이 "문장 $Y$는 참이다" 이면, 두 정점 $x, y$를 잇는 양방향 간선과 두 정점 $\neg x, \neg y$를 잇는 양방향 간선을 추가합니다.
  • 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 이면, 두 정점 $x, \neg y$를 잇는 양방향 간선과 두 정점 $\neg x, y$를 잇는 양방향 간선을 추가합니다.

 

이때 양방향 간선을 쓰는 이유는, 각 문장이 만드는 2가지 명제가 그 역 또한 성립하는 명제들이기 때문입니다.

 

- 그래프 탐색

그래프를 구성했으니 이제 그래프를 탐색하면서 문장 간의 모순을 발견하거나 답을 구해봅시다. 탐색은 아무 방법이나 괜찮다고 생각하지만 이 글에서는 DFS를 사용하겠습니다.

 

간선으로 이어진 두 정점은 둘 다 참이거나 둘 다 거짓입니다. 즉 같은 그룹에 속한다고 볼 수 있습니다. 여기서 모순을 발견하려면 그래프를 탐색하다가, $x$와 $\neg x$가 같은 그룹에 속하는지를 찾아주면 됩니다. $x$와 $\neg x$는 절대로 같은 그룹에 속할 수 없기 때문입니다.

이걸 효과적으로 해결하려면 각 정점을 2가지 색으로 칠하면 됩니다. DFS로 방문하는 정점들의 색을 전부 색 1로 칠하고, 방문한 정점의 역에 해당하는 정점을 색 2로 칠해줍시다. 만약 탐색 중에 색 2인 정점을 탐색해야 된다면 모순이라는 것을 알 수 있습니다.

 

모순이 없다면 탐색한 정점들 중 문장이 참이 되게 하는 정점, 즉 $\neg$ 가 붙지 않은 정점 중 색 1로 칠해진 것의 개수를 세면 참이 되는 문장의 개수를 구할 수 있습니다.

그런데 색 2로 칠해진 문장이 더 많다면 어떻게 해야 할까요? 이때는 그냥 색 1과 색 2를 바꾸면 결과가 똑같기 때문에, 그냥 둘 중에 더 많은 것을 쓰면 됩니다.

 

여기서 주의해야 할 점은, 그래프가 연결 그래프면 좋겠지만 연결 그래프가 아닐 수 있다는 것입니다. 따라서 그래프의 모든 연결 요소를 다 처리할 때 까지 DFS를 잊지 말고 돌려주도록 합시다!

 

시간 복잡도는,

  • DFS를 모든 정점에 대해 실행하고, 정점의 수가 $2N$, 간선의 수가 $2N$이므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.

 

공간 복잡도는,

  • 정점 $2N$개와 간선 $2N$개를 저장하므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.


소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

// 매 탐색마다 방문한 문장의 수
int group = 0;
// 매 탐색마다 방문한 문장 중, 문장을 참으로 만들면서 색 1로 칠해진 문장의 수
int colored = 0;

// DFS를 하는 함수입니다. 모순이면 true를, 그 외에는 false를 반환합니다.
bool dfs(vector<int> &truth, vector<vector<int>> &edges, int n, int v) {
    // 방문 중인 정점을 색 1로 칠합니다.
    truth[v] = 1;
    group++;
    
    // 현재 문장의 역에 해당하는 정점은 색 2로 칠합니다. 
    if (v > n) truth[v - n] = 2;
    else {
    	// 방문 중인 정점이 문장이 참이 되는 경우라면 개수를 세줍니다.
        colored++;
        truth[v + n] = 2;
    }
    
    bool result = false;
    for (int c: edges[v]) {
        if (truth[c] == 0) {
        	// 만약 이웃한 정점이 방문하기 전이라면, 탐색을 시도합니다.
            result = result || dfs(truth, edges, n, c);
        }
        else if (truth[c] == 2) {
            // 만약 이웃한 정점의 색이 색 2라면 모순입니다.
            return true;
        }
    }
    
    return result;
}

int main() {
    fastio;
    
    string ts = "true.";
    string fs = "false.";
    
    while (1) {
        int n;
        cin >> n;
        
        if (n == 0) break;
        
        vector<int> truth(2 * n + 1);
        vector<vector<int>> edges(2 * n + 1);
        
        for (int i = 1; i <= n; i++) {
            string sen;
            int j;
            
            cin >> sen >> j >> sen >> sen;
            
            // 문장 간의 사실 관계를 나타내는 그래프를 구축합니다.
            if (sen == ts) {
                edges[i].push_back(j);
                edges[j].push_back(i);
                edges[i + n].push_back(j + n);
                edges[j + n].push_back(i + n);
            }
            else {
                edges[i].push_back(j + n);
                edges[j].push_back(i + n);
                edges[i + n].push_back(j);
                edges[j + n].push_back(i);
            }
        }
        
        bool incons = false;
        int cnt = 0;
        for (int i = 1; i <= n && !incons; i++) {
        	// 아직 탐색하지 않은 문장이 있다면 DFS로 탐색하며 정점의 색을 칠합니다.
            if (truth[i] == 0) {
                // 각 탐색마다 탐색한 문장의 수, 참 문장의 수를 구합니다.
                group = 0;
                colored = 0;
                
                // 탐색을 시도합니다.
                if (dfs(truth, edges, n, i)) incons = true;
                else {
                    // 탐색이 성공적이라면 참이 될 수 있는 문장의 수를 더해줍니다.
                    cnt += max(colored, group - colored);
                }
            }
        }
        
        if (incons) {
            cout << "Inconsistent\n";
            continue;
        }
        
        cout << cnt << "\n";
    }
}

'Problem Solving > 백준' 카테고리의 다른 글

백준 10989 - 수 정렬하기 3  (0) 2023.10.10
백준 24461 - 그래프의 줄기  (0) 2023.10.10
백준 11616 - Digit Division  (0) 2023.10.01
백준 28251 - 나도리합  (0) 2023.09.27
백준 27925 - 인덕션  (0) 2023.09.26

문제 링크: https://acmicpc.net/problem/10989 

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net


문제를 요약해봅시다.

  • 주어진 $N$개의 수를 오름차순으로 정렬하여 출력합니다.

문제의 조건을 읽어보면 $N \le 10,000,000$으로 $N$의 제한이 매우 큰 것을 볼 수 있습니다.

이 정도 제한이면 병합 정렬이나 퀵 정렬같은 $O(N \log N)$의 시간복잡도를 갖는 정렬 알고리즘으로는 시간 제한에 맞추지 못할 수 있습니다. 엎친데 덮친 격으로 메모리 제한이 8MB이므로 $10,000,000$개 수를 다 저장하는 위의 알고리즘들로는 메모리 초과가 발생하게 됩니다.

따라서 널리 알려진 방법들은 사용할 수 없습니다. 어떻게 해야 할까요?

 

문제의 핵심은 주어지는 수들의 범위가 구간 $[1, 10000]$에 속한다는 것입니다.

수의 범위가 꽤 작기 때문에 각 수가 몇 번 등장했는지만 세어 주면 문제를 해결할 수 있습니다.

예를 들어 1 5 2 3 4 5 3 3 이 들어온다면 1이 1번, 2가 1번, 3이 3번, 4가 1번, 5가 2번이므로 1 2 3 3 3 4 5 5 를 얻을 수 있습니다.

 

시간복잡도는 입출력을 각각 $N$번 하므로 $O(N)$이고, 공간복잡도는 $O(10000) = O(1)$입니다.


소스코드 (C++)

더보기
#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    // 각 수가 몇 번 등장했는지 기록하는 배열입니다.
    vector<int> cnt(10001);
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        cnt[x]++;
    }
    
    // 기록된 횟수만큼 해당 수를 출력합니다.
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << "\n";
        }
    }
}

'Problem Solving > 백준' 카테고리의 다른 글

백준 5782 - This Sentence is False  (0) 2023.10.15
백준 24461 - 그래프의 줄기  (0) 2023.10.10
백준 11616 - Digit Division  (0) 2023.10.01
백준 28251 - 나도리합  (0) 2023.09.27
백준 27925 - 인덕션  (0) 2023.09.26

문제 링크: https://acmicpc.net/problem/24461 

 

24461번: 그래프의 줄기

그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 $0$이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다. 우리는 이 그래프의 정점 중에서 연결된

www.acmicpc.net


문제를 요약해봅시다.

  • 주어진 그래프는 사이클이 없고 간선이 $N - 1$개이므로 트리입니다.
  • 가장자리 정점은 연결된 간선이 1개인 정점이고, 줄기는 가장자리 정점이 2개 이하인 그래프입니다.
  • 트리의 가장자리 정점이 2개 이하가 될때까지 가장자리 정점을 지우는 것을 반복하고, 최후에 남은 정점의 목록을 출력해야 합니다.

이 문제는 주어진 내용을 구현하기만 하면 되는 문제입니다. 다음 과정을 반복하면 되는데요,

  • 간선의 개수가 1인 정점들을 모은 후,
  • 그 정점들을 모두 지우고, 연결되어 있던 정점들의 간선 수를 1개씩 줄입니다.

 

이는 위상 정렬 문제에서 볼 수 있는 기법과 비슷합니다. 답을 구현하기 위해서는 각 정점의 간선 수를 기록하는 배열과, 각 정점의 제거 여부를 기록하는 배열이 필요합니다. 위상 정렬 문제를 풀어보셨다면 쉽게 구현할 수 있습니다.

 

그러나 일반적인 위상 정렬 문제와 다르게 이 문제에서는 유의해야 할 부분이 있습니다. 매 반복마다 모든 정점이 동시에 제거된다는 것인데요.. 이는 매 반복마다 큐의 크기를 기록하고, 그 큐의 크기만큼만 반복하는 방법으로 구현하면 됩니다.

 

시간복잡도는,

  • 정점의 간선 수를 기록하는데 \(O(N)\)
  • \(O(N)\)개의 간선을 조사하므로 \(O(N)\)

 

총 \(O(N)\)의 시간복잡도를 갖습니다.


소스코드 (C++)

더보기
#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    vector<vector<int>> edges(n);
    vector<bool> exc(n);	// 정점의 제거 여부를 저장
    vector<int> neigh(n);	// 정점의 이웃 수를 저장
    
    // 그래프의 간선 배열을 만들고, 각 정점의 이웃 수를 계산합니다.
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        
        edges[u].push_back(v);
        edges[v].push_back(u);
        
        neigh[u]++;
        neigh[v]++;
    }
    
    // 가장자리 정점을 삽입하는 큐입니다.
    queue<int> q;
    
    // 가장자리 정점의 수를 셉니다.
    int ec = 0;
    for (int i = 0; i < n; i++) {
        if (neigh[i] == 1) {
            ec++;
        }
    }
    
    // 가장자리 정점의 수가 3개 이상이면 큐에 정점들을 삽입합니다.
    if (ec > 2) {
        for (int i = 0; i < n; i++) {
            if (neigh[i] == 1) {
                q.push(i);
                exc[i] = true;
            }
        }
    }
    
    // 그래프가 줄기만 남게 될때까지 가장자리 정점을 제거합니다.
    while (1) {
    	// 큐의 크기가 2 이하, 즉 그래프가 줄기만 남게 되면 종료합니다.
        int loop = q.size();
        if (loop <= 2) break;
        
        vector<int> next_elems;
        
        for (int i = 0; i < loop; i++) {
            int v = q.front();
            q.pop();
            
            // 큐에 담긴 정점들을 제거하고, 이웃한 정점들의 이웃 수를 1 줄입니다.
            for (int c: edges[v]) {
                if (!exc[c] && --neigh[c] == 1) {
                    next_elems.push_back(c);
                    q.push(c);
                }
            }
        }
        
        if (next_elems.size() <= 2) break;
        
        for (int x: next_elems) {
            exc[x] = true;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (!exc[i]) cout << i << " ";
    }
}

'Problem Solving > 백준' 카테고리의 다른 글

백준 5782 - This Sentence is False  (0) 2023.10.15
백준 10989 - 수 정렬하기 3  (0) 2023.10.10
백준 11616 - Digit Division  (0) 2023.10.01
백준 28251 - 나도리합  (0) 2023.09.27
백준 27925 - 인덕션  (0) 2023.09.26

+ Recent posts