진행중인 작업

2. 카드 베이스 구현

    2.1 카드의 이동 에 따른 케릭터 이동 구현

진행 예정 작업

1. AI

2. 스킬 베이스 구현

3. 스테이지 베이스 구현

4. 스테이지 이동 구현

5. NPC 플레이어 베이스 구현

6. 전투 준비단계 구현

7. 상점 구현

0. 디테일화 ( 베이스를 기반으로 스킬, 카드, 캐릭터, 적, 맵 추가작업 )

완료된 작업

1. 캐릭터 베이스 구현

2. 무기 베이스 구현

3. 플레이어 상호작용 구현

문제 설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.

맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• numbers 배열의 크기는 1 이상 1,000 이하입니다.
• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
• hand는 "left" 또는 "right" 입니다.
• "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

입출력 예

문제 해설

조건을 살펴보고 정리해보자.

• 먼저, 엄지손가락은 상하 좌우 4가지 방향만 이동할 수 있다.
• 왼쪽 열의 숫자는 항상 왼손을 사용한다.
• 오른쪽 열의 숫자는 항상 오른손 을 사용한다.
• 가운데 열의 4개 숫자는 두 엄지 손가락을 기준으로 가까운 엄지손가락을 사용한다.

이걸 코드로 구현하기 위해 다시 정리하면 다음과 같이 정리할 수 있다.

• 먼저, 각 키패드의 위치를 xy좌표도로 정리한다.
• 엄지 손가락의 거리측정방식은 멘하탄 방식의 거리측정방식을 사용해야 한다. 4방향으로 이동하기 때문이다.
• 왼쪽, 오른쪽은 담당하는 손가락의 위치만 갱신해준다.
• 중앙의 측정방식에, 멘하탄 방식의 거리측정을 사용하고 같을경우 주어진 손으로 갱신해준다.

유클리드 방식이 아닌 멘하탄 방식의 거리측정방식 을 사용하도록 유의하자.

첫 번째 시도

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef string (*FuncPtr)(const vector<int>&,vector<int>&,vector<int>&, const string&);

string InputL(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    handL = numberVector2D;
    return "L";
}
string InputR(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    handR = numberVector2D;
    return "R";
}

float GetDistance(const vector<int>& A, const vector<int>& B)
{
    return sqrt(pow(A[0] - B[0], 2) + pow(A[1] - B[1], 2));
}

string ChackDistance(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    float distanceR = GetDistance(numberVector2D, handR);
    float distanceL = GetDistance(numberVector2D, handL);
    
    if (distanceR < distanceL) {
        handR = numberVector2D;
        return "R";
    }
    else if (distanceR > distanceL) {
        handL = numberVector2D;
        return "L";
    }
    else if (hand[0] == 'l') {
        handL = numberVector2D;
        return "L";
    }
    else if (hand[0] == 'r') {
        handR = numberVector2D;
        return "R";
    }
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    unordered_map<int, vector<int>> PointAndVector2D;
    unordered_map<int, FuncPtr> PointAndFuntion;

    for (int i = 0; i < 9; i++) PointAndVector2D[i+1] = { i / 3, i % 3};
    PointAndVector2D[0] = { 1, 3 };

    PointAndFuntion[0] = ChackDistance;
    PointAndFuntion[1] = InputL;
    PointAndFuntion[2] = ChackDistance;
    PointAndFuntion[3] = InputR;
    PointAndFuntion[4] = InputL;
    PointAndFuntion[5] = ChackDistance;
    PointAndFuntion[6] = InputR;
    PointAndFuntion[7] = InputL;
    PointAndFuntion[8] = ChackDistance;
    PointAndFuntion[9] = InputR;

    vector<int> StartL = {0, 3};
    vector<int> StartR = {2, 3};

    for (auto& def : numbers)
        answer += PointAndFuntion[def](PointAndVector2D[def], StartR, StartL, hand);

    return answer;
}

실패

어차피 숫자의 개수는 정해져있기 때문에, 좌표도와 함수포인터 를 정리하고,

지정된 좌표의 해시키값에 정해진 함수를 밀어넣으면 된다.

그러면, numbers의 탐색시간은 O(N)을 보장한다.

유클리드 방식의 거리측정을 사용했다. 이걸 멘하탄 거리측정방식 으로 바꾸면 성공한다.

두 번째 시도

#include <string>
#include <vector>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef string (*FuncPtr)(const vector<int>&,vector<int>&,vector<int>&, const string&);

string InputL(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    handL = numberVector2D;
    return "L";
}
string InputR(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    handR = numberVector2D;
    return "R";
}

float GetDistance(const vector<int>& A, const vector<int>& B)
{
    return abs(A[0] - B[0]) + abs(A[1] - B[1]);
}

string ChackDistance(const vector<int>& numberVector2D, vector<int>& handR, vector<int>& handL, const string& hand)
{
    float distanceR = GetDistance(numberVector2D, handR);
    float distanceL = GetDistance(numberVector2D, handL);
    
    if (distanceR < distanceL) {
        handR = numberVector2D;
        return "R";
    }
    else if (distanceR > distanceL) {
        handL = numberVector2D;
        return "L";
    }
    else if (hand[0] == 'l') {
        handL = numberVector2D;
        return "L";
    }
    else if (hand[0] == 'r') {
        handR = numberVector2D;
        return "R";
    }
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    unordered_map<int, vector<int>> PointAndVector2D;
    unordered_map<int, FuncPtr> PointAndFuntion;

    for (int i = 0; i < 9; i++) PointAndVector2D[i+1] = { i % 3, i / 3};
    PointAndVector2D[0] = { 1, 3 };

    PointAndFuntion[0] = ChackDistance;
    PointAndFuntion[1] = InputL;
    PointAndFuntion[2] = ChackDistance;
    PointAndFuntion[3] = InputR;
    PointAndFuntion[4] = InputL;
    PointAndFuntion[5] = ChackDistance;
    PointAndFuntion[6] = InputR;
    PointAndFuntion[7] = InputL;
    PointAndFuntion[8] = ChackDistance;
    PointAndFuntion[9] = InputR;

    vector<int> StartL = {0, 3};
    vector<int> StartR = {2, 3};

    for (auto& def : numbers)
        answer += PointAndFuntion[def](PointAndVector2D[def], StartR, StartL, hand);

    return answer;
}

성공

멘하탄 방식을 사용했다.

4방향이기 때문에 대각선을 고려하지 않아도 된다.

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.

원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

입출력 예

문제 해설

단순하게 for문을 3중으로 돌려서 해결할 수 있다.

연속하는 부분 수열을 얻기 위해서 1부터 다시 1까지 돌아와야 하기 때문에, 범위끝까지 넘어갔을 경우 다시 첫번째 값으로 돌아오는 함수를 만들어서 사용해야 한다.

첫 번째 for문은 탐색해야 하는 수열의 개수를 정하는 for문

두 번째 for문은 전체 수열을 탐색하는 for문

세 번째 for문은 첫번째 for문에서 정해진 개수만큼 중첩으로 더하는 for문

이렇게 3개의 for문을 사용하면 된다.

중복되는 데이터를 무시하는 방법은 set을 사용하여 해결할 수 있다.

첫 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;
int getNum(const vector<int>& elements, int find)
{
    return elements[find % elements.size()];
}
int solution(vector<int> elements) {
    int answer = 0;
    set<int> answerset;
    for(int i = 0; i < elements.size(); i++)
    {
        for(int j = 0; j < elements.size(); j++)
        {
            int now = elements[j];
            for(int k = j; k < j + i; k++) now += getNum(elements, k);
            answerset.insert(now);
        }
    }
    
    return answerset.size();
}

실패

순환방식은 옳으나, 첫 번째 값이 두번 탐색되는 경우가 있었다. 세 번째 for문의 k = j부분을 k = j + 1에 k <= j + i 로 수정하면 해결된다.

두 번째 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;
int getNum(const vector<int>& elements, int find)
{
    return elements[find % elements.size()];
}

int solution(vector<int> elements) {
    unordered_set<int> answerset;
    for(int i = 0; i < elements.size(); i++)
    {
        for (int j = 0; j < elements.size(); j++)
        {
            int now = elements[j];
            for (int k = j+1; k <= j + i; k++) 
                now += getNum(elements, k);
            answerset.insert(now);
        }
    }
    
    return answerset.size();
}

성공

오류를 해결한 뒤 set을 unordered_set으로 고쳐서 조금이나마 데이터 탐색속도를 증가시켰다.

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

입출력 예

문제 해설

조건항을 생각해보자.

가장 최소의 가짓수가 되도록 귤을 가져가야한다.

쉽게 말해

가장 많은개수를 가지는 사이즈의 귤 을 찾아야 한다.

사이즈는 중요하지 않다. 그냥 종류가짓수가 가장 적으면 되기 때문.

가장 많은 양의 귤을 정리한다음, 해당 귤 개수만큼 가져가면 그게 결국 최솟가짓수 이기 때문.

첫 번째 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> count(10000000, 0);
    for (auto& def : tangerine) count[def]++;
    sort(count.rbegin(), count.rend());
    
    for (auto& def : count)
    {
        if (k <= 0) break;
        k -= def;
        answer++;
    }
    return answer;
}

실패

vector로 최댓수 만큼 배열을 만든다음, 해당 배열의 번째가 귤의 사이즈 라고 생각하고 그 위치에 찾은 귤 개수마다 1씩 더하면 된다.

그리고, 역순 정렬을 한다음, 가장 첫번째 값부터 k에서 빼내서 0보다 작아지면 끝. answer에 넣은 갯수만큼 반환하면 된다.

최대갯수가 10,000,000 이상이기 때문에, 10,000,000 이 아니라 10,000,001 개만큼 배열을 만들어야 한다. 이걸 실수했다.

두 번째 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> count(10000001, 0);
    for (auto& def : tangerine) count[def]++;
    sort(count.rbegin(), count.rend());
    
    for (auto& def : count)
    {
        if (k <= 0) break;
        k -= def;
        answer++;
    }
    return answer;
}

성공

오류를 수정했다.

3인칭 FPS게임의 기본사항인 3인칭뷰 와 1인칭 뷰를 전환하면서 사용할 수 있다.

Aim과 Hip에 대한 애니메이션 전환을 사용할 수 있다.

ABP 재설정

컨듀잇과 스테이트 에일리어스 를 사용하여 ABP의 간선을 정리한다.

컨듀잇(Conduit)

ABP에서 애니메이션 끼리의 연결과정이 너무 복잡해질 때 사용한다.

일정 조건 하에 컨듀잇 으로 애니메이션 노드가 이동하게 되며, 컨듀잇에서 노드를 재정리한다.

Is Aiming이 컨듀잇 이다.

컨듀잇에 들어온 노드는, 해당사항이 있을 경우, 내려가는 노드로 이동한다.

위 이미지에서는 해당되는 bool값이 false일경우 좌측, true일경우 우측으로 애니메이션 노드를 이동시킨다.

스테이트 에일리어스(State Alias)

애니메이션 노드의 지정된 조건이 True가 되었을 경우 연결된 에니메이션 스테이트 를 실행하는 역할을 한다.

주로, 복잡해진 애니메이션 스테이트들의 연결을 최적화하기 위해 사용된다.

애니메이션 재설정을 위해 데이터를 정의한다.

노드 연결은 위와 같다.

Movement에서 애니메이션의 행동을 연결하고, Turn시, 지정된 Turn애니메이션을 실행한 뒤에 IsAiming인 컨듀잇을 통과하여 현재 상태가 Aim인지 아닌지 확인하고, Movement로 복귀할지, RifleAiming으로 복귀할지 판단 이동한다.

Aiming_To_HipFire와 HipFire_To_Aiming은 조준상태를 판별하기 위한 노드이다.

노드에서 사용하는 bool은 다음 한개를 사용한다.

bool bAiming

ABP에 전달하는 Bool값 연동.

먼저, 키값에 사용하는 Bool을 컨트롤 해야하기 때문에, 인풋값을 연동해준다.

#pragma once

#include "CoreMinimal.h"
#include "FTPSGameCharacter.h"
#include "Actors/BaseCharacter.h"
#include "Datas/CharacterStruct.h"
#include "Hero.generated.h"

class IInteract;
class UInputMappingContext;
class UInputAction;

/**
 * 
 */
UCLASS()
class FTPSGAME_API AHero : public ABaseCharacter
{
	GENERATED_BODY()

	// Components
	UPROPERTY(VisibleDefaultsOnly, Category = Camera)
	TObjectPtr<USpringArmComponent> SpringArm;

	UPROPERTY(EditDefaultsOnly, BlueprintReadWrite, Category = Camera, meta = (AllowPrivateAccess = "true"))
	TObjectPtr<UCameraComponent> Camera;
	
	// Input Actions
	UPROPERTY(EditDefaultsOnly, Category = Input, meta=(AllowPrivateAccess="true"))
	TObjectPtr<UInputAction> MoveAction;

	UPROPERTY(EditDefaultsOnly, Category = Input, meta=(AllowPrivateAccess="true"))
	TObjectPtr<UInputAction> ViewAction;

	UPROPERTY(EditDefaultsOnly, Category = Input, meta=(AllowPrivateAccess="true"))
	TObjectPtr<UInputAction> JumpAction;

	UPROPERTY(EditDefaultsOnly, Category = Input, meta=(AllowPrivateAccess="true"))
	TObjectPtr<UInputMappingContext> InputMappingContext;

	UPROPERTY(EditDefaultsOnly, Category = Input, meta=(AllowPrivateAccess="true"))
	FInputStruct CombatInput;


	
public:
	AHero();

	virtual void SetupPlayerInputComponent(class UInputComponent* PlayerInputComponent) override;

	void CameraHold(bool bValue);
	virtual FVector GetControlLocation() override;
	
private:
	virtual void BeginPlay() override;

private:
	void Move(const FInputActionValue& Value);
	void View(const FInputActionValue& Value);

	void SelectMainHolder();
	void SelectSubHolder();



	virtual void Interact() override;
	virtual void InteractCanceled() override;
	virtual void InteractComplete() override;
	

	void BindingDefaultActions(UEnhancedInputComponent* EnhancedInputComponent);
	void BindingCombatActions(UEnhancedInputComponent* EnhancedInputComponent);

protected:
	virtual void AimingDownSight() override;

	UFUNCTION(BlueprintNativeEvent)
	void Aiming();

	UFUNCTION(BlueprintNativeEvent)
	void HipFire();


};

void AHero::Aiming_Implementation()
{
	Super::Aiming();
	bAiming = true;
	bAimingDownSight = false;
	CameraHold(true);
}

void AHero::HipFire_Implementation()
{
	Super::HipFire();
	bAiming = false;
	bAimingDownSight = false;

	CameraHold(false);
}

void AHero::BindingCombatActions(UEnhancedInputComponent* EnhancedInputComponent)
{
	// Interact
	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("Interact"), ETriggerEvent::Ongoing, this, &AHero::Interact);
	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("Interact"), ETriggerEvent::Canceled, this, &AHero::InteractCanceled);

	// Select Holder
	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("MainHolder"), ETriggerEvent::Triggered, this, &AHero::SelectMainHolder);
	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("SubHolder"),  ETriggerEvent::Triggered, this, &AHero::SelectSubHolder);

	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("AimingDownSight"), ETriggerEvent::Ongoing, this, &AHero::Aiming);
	EnhancedInputComponent->BindAction(*CombatInput.InputActionMap.Find("AimingDownSight"), ETriggerEvent::Completed, this, &AHero::HipFire);
}

위와같이 AimingDownSight키값을 연동해서 마우스 우측클릭을 했을 때 조준할 수 있도록 해준다.

C++에서 정의해놓은 input Action Map에 집어넣어준다.

카메라 무브먼트 설정

3인칭 FPS게임에서 조준했을 때, 1인칭처럼 카메라가 이동하는건 흔한 방식이다. 이러한 방식을 구현해보자.

조준했을 때 타임라인의 키프레임값을 활용하여 카메라의 FOV와 Y값을 조정할 것이다.

타임라인은 위와같이 조정한다. 처음 FOV값은, 90 마지막값은 45로,

CameraY값은 처음값은 0에 마지막값은,50으로 조정한다.

카메라의 Play와 Reverse에 이벤트그래프를 연결하여 조정한다.

Play시에는 정방향으로, Reverse시 에는 역방향으로 값이 이동된다.

Camera의 Y값을, FieldOfView는 FOV값을 집어넣어 조정한다.

테스트

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

문제 해설

DFS와 BFS 둘다 사용할 수 있는 문제이다.

x에 n을 더하는것,

x에 2를 곱하는것,

x에 3을 곱하는것,

의 3가지 경우를 깊이우선탐색, 너비우선탐색으로 돌리고 경우의수가 나타났을 때 종료하면 된다.

DFS의 경우는 제귀를 사용하고

BFS의 경우는 queue와 hash_map또는hash_set을 사용한다.

단!, DFS는 시간초과로 실패하는 경우가 있음으로 가능한 BFS로 실행할것.

첫 번째 시도

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(int x, int y, int n) {
    queue<vector<int>> count;
    count.push({ x, 0 });
    while (!count.empty() && count.front()[0] != y)
    {
        vector<int> now = count.front();
        count.pop();
        if (now[0] * 2 <= y) count.push({now[0] * 2, now[1]+1});
        if (now[0] * 3 <= y) count.push({now[0] * 3, now[1]+1});
        if (now[0] + n <= y) count.push({now[0] + n, now[1]+1});                     
    }
    if (count.empty()) return -1;
    return count.front()[1];
}

실패

BFS형태로 시도하였으나 실패하였다, 정방향으로 x값을 중첩시켜서 나아가는 형태로 구상하였으나, 중첩된 경우의 수가 나타날 수 있음으로 그걸 고려하지 못했다.

또한, 곱셈으로 나타나게 되면 결국 최종적으로 도착하지 못하는 경우를 예측하지 못한다.

예를들어, y를 3으로 나누었을 때, x로 도달해야 하는데, 3으로 나누었을 때 나머지값이 나타나거나,

2로 나누었을 때 x로 도달해야 하는데 2로 나누었을 떄 나머지값이 나타나면 결국 도달하지 못한다고 볼 수 있다.

그럼으로, 정방향으로 접근하는것 보다 역방향으로 접근하는게 더효율적이다.

두 번째 시도

#include <string>
#include <vector>
#include <set>

using namespace std;

set<int> chack;

void DFS(const int& x, int y, const int& n, int count = 0)
{
    if (!chack.empty() && *chack.begin() < count) return;
    if ((y / 3) * 3 == y && y / 3 >= x)
        DFS(x, y / 3, n, count+1);
    if ((y / 2) * 2 == y && y / 2 >= x)
        DFS(x, y / 2, n, count + 1);
    if (y - n >= x)
        DFS(x, y - n, n, count + 1);
    if (y == x)
        chack.insert(count);
}

int solution(int x, int y, int n) 
{
    DFS(x, y, n);
    if (chack.empty()) return -1;
    return *chack.begin();
}

실패

깊이우선탐색으로 역방향 접근을 진행하였다.

접근방법이 옳고, 정답이 나타나나 11번 문항이 시간초과가 나타난다. 즉, 중첩된 연산값을 제외해야한다는 뜻.

해당 접근방식을 고려하여 DFS가 아니라 BFS가 유효함을 이해할 수 있다.

세 번째 시도

#include <string>
#include <vector>
#include <set>
#include <queue>
#include <unordered_set>

int solution(int x, int y, int n) {
    std::queue<std::pair<int, int>> q;
    std::unordered_set<int> visited;

    q.push({y, 0});
    visited.insert(y);

    while (!q.empty()) {
        int current = q.front().first;
        int count = q.front().second;
        q.pop();

        if (current == x) {
            return count;
        }

        if (current % 3 == 0 && current / 3 >= x && visited.find(current / 3) == visited.end()) {
            q.push({current / 3, count + 1});
            visited.insert(current / 3);
        }
        if (current % 2 == 0 && current / 2 >= x && visited.find(current / 2) == visited.end()) {
            q.push({current / 2, count + 1});
            visited.insert(current / 2);
        }
        if (current - n >= x && visited.find(current - n) == visited.end()) {
            q.push({current - n, count + 1});
            visited.insert(current - n);
        }
    }

    return -1;
}

성공

BFS형태의 접근방법을 고려하였다.

중첩연산을 생각해서, 전에 접근하였던 int값이라면, 이미 접근하였었음으로 다시한번 생성할 필요가 없기 때문에 제외하고.

역순으로 접근하여 나누었을 때, 나머지값이 0이 나타나야 하기 때문에 나머지값이 0이 아니라면 결과가 나타날 수 없어, 고려하지 않는다.

즉, 결괏값 에서 초기값으로 연산하는 과정에 연산했던 중복값을 처리하는걸 피하게 되면 성공한다.