그래프

인접 리스트

인접 리스트는 연결된 노드만 리스트에 저장하는 방식이다.
아래와 같이 표현할 수 있다.

A -> B,D
B -> A,C,D
C -> B,D
D -> A,B,C

• 장점
  • 필요한 정보만 저장하므로 메모리를 절약할 수 있다.
  • 그래프 탐색 시 인접 노드를 빠르게 찾을 수 있다.
• 단점
  • 특정 노드가 다른 노드와 연결되어 있는지 확인하는데 O(V)의 시간이 걸릴 수 있음

코딩 테스트에선 보통 인접 리스트 방식이 더 사용된다. 이유는

• 메모리 효율성이 뛰어남
  • 인접 행렬은 O(V^2)의 공간을 차지하기 때문에, 노드 개수(V)가 크면 메모리를 과도하게 사용한다.
    반면, 인접 리스트는 O(V + E)의 공간만 필요하므로, 노드가 많고 간선이 적은 경우(희소 그래프, Sparse Graph)에 훨씬 적은 메모리를 사용하게 된다.
• 탐색 속도가 빠름
  • 인접 리스트는 O(E)에 가깝지만, 인접 행렬은 O(V^2)가 될 수 있다.
• 실제 입력 데이터가 인접 리스트 형태인 경우가 많음
  • 대부분의 코딩 테스트 문제에서 그래프 입력은 a → b (weight) 형태로 주어지는데, 이를 인접 행렬로 변환하는 것보다 인접 리스트로 저장하는 것이 더 자연스럽다.

---

DFS(깊이 우선 탐색)

DFS(Depth First Search)는 깊이 우선 탐색이라는 의미로 트리나 그래프를 최대한 깊게 들어가서 탐색하는 방법이다.

DFS는 재귀나 스택을 이용해서 구현할 수 있다.

• 장점
  • 깊이 우선 탐색이 유리한 문제에 적합하다.
    • 미로 풀이 같은 데에 사용하기 좋다.
    • 모든 경우의 수(혹은 모든 경로)를 찾거나, 퍼즐을 푸는 문제들이 나오는 경우가 있는데 이럴 때 DFS로 모든 가능한 선택지를 일단 끝까지 가보는 식으로 푼다.
• 단점
  • 재귀로 구현할 시 트리의 깊이가 매우 깊으면 스택 오버플로우가 발생할 수 있다.

---

BFS(너비 우선 탐색)

BFS(Breadth First Search)는 너비 우선 탐색이라는 의미로 트리의 같은 레벨에 있는 노드들을 먼저 방문 후에 다음 레벨로 이동해 탐색하는 방식이다.

BFS는 큐 자료구조를 이용해 구현할 수 있다.
예를 들어, 아래와 같은 트리를 BFS로 탐색한다고 가정해보면

      A
     / \
    B   C
   / \   \
  D   E   F

BFS 탐색 순서는 A → B → C → D → E → F 순서이다.
이 순서를 어떻게 큐를 사용해 구현하면

BFS 탐색 과정

1. 처음에는 루트 노드 A를 큐에 넣는다.
   • 큐 상태: [A]
2. 큐에서 A를 꺼내고, A의 자식들 B와 C를 큐에 넣는다.
   • 큐 상태: [B, C] → 탐색: [A]
3. 큐에서 B를 꺼내고, B의 자식들 D와 E를 큐에 넣는다.
   • 큐 상태: [C, D, E] → 탐색: [A, B]
4. 큐에서 C를 꺼내고, C의 자식 F를 큐에 넣는다.
   • 큐 상태: [D, E, F] → 탐색: [A, B, C]
5. 큐에서 D를 꺼내고, D는 자식이 없으므로 아무것도 하지 않는다.
   • 큐 상태: [E, F] → 탐색: [A, B, C, D]
6. 큐에서 E를 꺼내고, E는 자식이 없으므로 아무것도 하지 않는다.
   • 큐 상태: [F] → 탐색: [A, B, C, D, E]
7. 큐에서 F를 꺼내고, F는 자식이 없으므로 아무것도 하지 않는다.
   • 큐 상태: [] → 탐색: [A, B, C, D, E, F] → 탐색 종료

이렇게 큐를 이용하면 너비 기반 탐색과 동일하게 탐색을 할 수 있다.
FIFO(선입선출)이기 때문에 먼저 들어온 노드들이 먼저 처리되기 때문에, 같은 레벨에 있는 노드들(B와 C)가 먼저 탐색되고, 그다음 레벨인 D, E, F가 탐색된다.

• 장점
  • 최단 경로 탐색에 유리하다.
  • BFS는 루트에서 가장 가까운 노드부터 탐색하는 방법이기 때문에 루트에서부터 노드까지의 레벨이 낮을수록 경로가 짧아진다.
  • 다시 말해, 루트에서 해당 노드까지 가는 길의 깊이가 짧을수록 그 경로가 더 짧은 경로이다.
  • 위의 트리 기준으로 루트에서 레벨 1에 있는 노드들(B, C)이 가장 가까운 경로를 가지며, 레벨 2에 있는 노드들(D, E, F)는 그보다 더 먼 경로를 가지고 있다
• 단점
  • 큐에 노드를 계속 저장해야 하므로, 메모리 사용량이 많아질 수 있다.

---

커맨드 패턴

커맨드 패턴은 자신의 행동을 실행하고 Undo로 돌아갈 수 있는(혹은 그와 같은 효과를 내는) 패턴이다.
포토샵 같은 프로그램 문서 툴 등등에 쓰이는 대표적인 패턴 중 하나다.

내가 알기론 행동을 class같은 데이터로 만들어 일정량을 Stack 같은 곳에 저장하고 하나씩 빼면서 Undo할 수 있는 걸로 안다.

class ICommand
{
public:
	virtual void Execute() = 0;
	virtual void Undo() = 0;
	virtual ~ICommand() {}
};

class Light
{
public:
	void TurnOn()
	{
		std::cout << "불을 켭니다." << std::endl;
	}

	void TurnOff()
	{
		std::cout << "불을 끕니다." << std::endl;
	}
};

class LightOnCommand : public ICommand
{
private:
	Light* light;

public:
	LightOnCommand(Light* l) : light(l) {}

	void Execute() override
	{
		light->TurnOn();
	}

	void Undo() override
	{
		light->TurnOff();
	}
};

class LightOffCommand : public ICommand
{
private:
	Light* light;

public:
	LightOffCommand(Light* l) : light(l) {}

	void Execute() override 
	{
		light->TurnOff();
	}

	void Undo() override
	{
		light->TurnOn();
	}
};

class RemoteControl
{
private:
	ICommand* command;

public:
	void setCommand(ICommand* c)
	{
		command = c;
	}

	void pressButton()
	{
		command->Execute();
	}

	void pressUndo()
	{
		command->Undo();
	}
};


int main()
{
	Light livingRoomLight;

	LightOnCommand lightOn(&livingRoomLight);
	LightOffCommand lightOff(&livingRoomLight);

	RemoteControl remote;

	// 불 켜기 명령 실행
	remote.setCommand(&lightOn);
	remote.pressButton();

	// 불 끄기 명령 실행
	remote.setCommand(&lightOff);
	remote.pressButton();

	// 직전 명령 취소 (불 켜기)
	remote.pressUndo();

	return 0;
}

---

여행경로 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

bool Travel(int index, vector<vector<string>>& leftTickets, vector<string>& travels)
{
	vector<string> ticket = leftTickets[index];
	string now = ticket[1];

	travels.push_back(now);
	leftTickets.erase(leftTickets.begin() + index);

	bool result = false;
	for (int i = 0; i < leftTickets.size(); i++)
		if (now == leftTickets[i][0])
			result |= Travel(i, leftTickets, travels);

	//중간에 이거 안되는데? 하면 다시 leftTrickets를 채워서 뒤로 보내야돼
	//완료면 그 계산은 거기서 끝

	if (result)
		return true;
	else
	{
		if (leftTickets.size() == 0)
			return true;
		else
		{
			if (index < leftTickets.size())
				leftTickets.insert(leftTickets.begin() + index, ticket);
			else
				leftTickets.push_back(ticket);
			
			travels.pop_back();

			return false;
		}
	}
}

vector<string> solution(vector<vector<string>> tickets)
{
	for (int i = 0; i < tickets.size() - 1; i++)
		for (int j = 0; j < tickets.size() - 1; j++)
			if (tickets[j][0] > tickets[j + 1][0] || tickets[j][1] > tickets[j + 1][1])
				swap(tickets[j], tickets[j+1]);

	vector<string> travels;
	for (int i = 0; i < tickets.size(); i++)
		if (tickets[i][0] == "ICN")
		{
			travels.push_back("ICN");

			vector<vector<string>> clone(tickets);
			Travel(i, clone, travels);

			if (clone.size() == 0)
				break;

			//실패했으면 초기화
			travels.clear();
		}

	return travels;
}

Graph 혹은 map을 이용해 푸는게 훨씬 편하고 빨랐을 것 같다.
데이터를 정리하고 DFS를 하는게 훨씬 맞는 방식이었던 것 같다.

중간에 sort(tickets.begin(), tickets.end(), [](vector<string>& first, vector<string>& second))를 이용해 sort를 하려고 했는데 계속 assert가 떠서 원인을 모르겠어서 그냥 직접 정렬했다.

---

무조건 int를 쓰지 말고 int32를 써라

레퍼런스 타입으로 다른 곳에 공개할 때 Get이 아닌 Acess를 붙여 공개하는게 좋아보임
예)
const FString& GetName();
FString& AcessName();