석유 시추 bfs 로  석유를 미리 번호를 지어두는 작업이 필요하다고 생각한다.

그리고 좌측부터 1자로 내리면서  제일큰걸 확인해보면 되는문제라 생각한다.

해당문제라면

1 [ 0,0], [ 0,1] [ 0,2] [ 0,3] [ 0,4]....  12

2 [2,0] [ 2,1] [ 2,2] 3

....

재귀로 bfs 탐색을하며 해당처럼 데이터를 모아준다

모아두었기때문에 한번 건들인 석유를 두번 캐지않을수있다.

#include <string>
#include <vector>
#include <unordered_map>
#include<queue>
using namespace std;


static int const nextland[4][2]{ {0,1}, {1,0}, {-1,0}, {0,-1} };

//석유 룰 묶어주는 함수
void find_oil(vector<vector<int>>& land, int x, int y, int& oil_count, unordered_map<int, int>& oil_monny) {
	queue<tuple<int, int>> nextxy;
	nextxy.push(make_tuple(x, y));
	land[x][y] = oil_count;
	oil_monny[oil_count]++;
	while (nextxy.size() != 0)
	{


		tuple<int, int> nxy = nextxy.front();
		int xy[2]{ get<0>(nxy),get<1>(nxy) };
		nextxy.pop();


		int x, y = 0;
		for (auto arrow : nextland) {
			y = arrow[1] + xy[1];
			x = arrow[0] + xy[0];
			if (x >= 0 && x < land.size() && y >= 0 && y < land[0].size() && land[x][y] == 1) {
				land[x][y] = oil_count;
				oil_monny[oil_count]++;
				nextxy.push(make_tuple(x, y));
			}
		}
	}
	oil_count++;
}

int solution(vector<vector<int>> land) {
	int answer = 0;
	int oil_count = 2;
	unordered_map<int, int> oil_monny;

	for (int i = 0; i < land.size(); i++) {
		for (int j = 0; j < land[i].size(); j++) {
			if (land[i][j] == 1) {
            
            //석유를 한번에 모아주고 그 모은 석유의 벨류 탐색
				find_oil(land, i, j, oil_count, oil_monny);
			}
		}
	}


	for (int i = 0; i < land[0].size(); i++) {
		vector<bool>c(oil_count - 2);
		int b =0;
		for (int j = 0; j < land.size(); j++) {
        //아래로 내리면서 기름 있는땅 찾고 만약 탐색 안되었으면
			if (land[j][i] > 1 && (c[land[j][i] - 2] == false)) {
            //탐색완료 표시
				c[land[j][i] - 2] = true;
				// 현재 벨류 추가
                b += oil_monny[land[j][i]];
			}
		}
		if (answer < b) {
			answer = b;
		}
	}

	return answer;
}

알고리즘 문제 해결전략 1편 발췌

예전에 해당 책을 읽다 기억에 오래 남았던 문제 한가지가

해당문제다 결과값이  ㅡ2 이여야 할거같지만
위 이미지처럼 4294967294가 나온다.

해당값이 나오는 이유를 아래를 보기전에 생각해보자




a: unsigned char   , b: short
                   (a  + b ) :int    *  c : int
         (a+b) *c : int  + d unsigned int
           (a+b)*c+d : unsigned int

마지막 전체 수식의 답을 계산하는부분.
 d를 더하면서 전체 수식이 부호없는 정수형으로 변환 되는데 

-2 는 자료형에 담기에 너무작은 값이기 때문에 오버플로우가 일어나
값이 강제로 부호없는 정수로 캐스팅 되는 과정에서 큰값이 된다.

그렇기때문에 문제처럼 
unsigned를 쓸때 auto캐스팅을 조심하는게 좋다

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

문제가 길다

간단 하게 설명하자면

그래프들은 1개이상의 정점과 정점들을 연결하는 단방향 간선 으로 이루어져 있다.

위 처럼 도넛 모양 그래프 막대모양 그래프 8자모양 그래프가 여러가지 있다.

그래프들과 무관한 정점을 하나 생성한뒤 그래프들을  임의의정점 하나로 향하는 간선들을 연결하였다.

그후 각 정점에 서로 다른 번호를 매겼다.

생성한 정점의 번호와 정점을 생성하기전 그래프들의 수를 구해야 한다.

return [생성한 정점의 번호, 도넛모양 그래프수,막대모양 그래푸수,8자모양그래프수]

해당 문제의 입출력 예제를 보자면

1번 = 도넛모양

4->3 = 막대모양 그래프

2 = 임의의 정점 

그럼으로 return [2,1,1,0]

정점들을 탐색하며 노느들이 해당하는 정보를 알면되는 간단한 문제다.

간선은 단방향 단선뿐이며,  

노느들의 특징은

도넛모양은 시작위치에서 모든 노드들을 한번씩 거친후 다시 첫 노드로 돌아온다는것이다.

단방향노드는 마지막노드까지 탐색후 끝난다.

8자모양 그래프는 시작노드로 오기전 중간노드를 거친후 돌아온다

도넛모양과 유사하지만 같은노드를 다시 만났을때 처음 시작한 노드가 아니라는 점이 다르다.

해당문제는 시작 노드와 간선들의 특징만 생각하면 어렵지않다.

map 에 정점과 간선들을 추가해주면서

특징들을 확인하기위해 

간선이 나가는 횟수와

자신을 가리키는 간선이 있는지 확인한다 

	unordered_map<int, vector<int>> map;
for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}

 간선이 나가는 수를 저장했던 edin을 반복하면 노드들을 전부 탐색한다

제일크며 Bedin로 나에게 도착했던간선이 없는 노드를 찾으면

시작부분일것이다

단방향 간선이 존재하기에 간선수를 추가로 확인했다.

	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

시작 노드에서 나가는 그래프들을 전부 돌면서 무슨 그래프인지만 알아내면 된다.

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}

만약  현재노드의간선이 없다면? 직선 2번

다시도착한게 size가 1이상이면 8번

다음 간선이 start 까지 도착했다면 도넛모양

다음노드 탐색

int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

#include<queue>
#include <unordered_map>
#include<vector>
#include<iostream>

using namespace std;
int star = 0;
int Solution_find(unordered_map<int, vector<int>>& m, int num) {
	if (m[num].size() > 1)return 3;
	if ((m[num].size() == 0)) return 2;
	if (m[num][0] == star) return 1;
	for (int i = 0; i < m[num].size(); i++)
		return Solution_find(m, m[num][i]);
}

vector<int> solution(vector<vector<int>> edges) {

	vector<int> answer(4);

	unordered_map<int,int> edin;
	unordered_map<int,bool> Bedin;
	int start_N = 0;
	unordered_map<int, vector<int>> map;
	for (auto e : edges) {
		map[e[0]].push_back(e[1]);
		edin[e[0]]++;
		Bedin[e[1]] = true;
	}
	int s = 0;
	for (auto i : edin) {
		if (s < i.second && !Bedin[i.first])
		{
			s = i.second;
			start_N = i.first;
		}
	}
	answer[0] = start_N;

	for (auto num : map[start_N]) {
		star = num;
		answer[Solution_find(map, num)]++;
	}


	return answer;
}

토마토마토마토

https://www.acmicpc.net/problem/7576

익지 않은 토마토는 근처 토마토를 익게 하는 문제 

혼자 익는경우가 없을때

모든 토마토가 익을때까지 최소일수 를 구하는 문제

간단하게 BFS 를 써서 푸는 문제다 

골드 5인만큼 그냥 시뮬레이션 돌리면 풀린다.

#include<iostream>
#include<vector>
#include<queue>
#include <tuple>
using namespace std;

#define XYZ tuple<int,int>

vector<XYZ> nonfire;
const XYZ MoverDirection[4] = { {1,0} ,{-1,0} ,{0,-1} ,{0,1} };
vector<vector<int>> vec;
int N = 0, H = 0;

///토마토 익는칸 확인 함수
vector<XYZ> findNextTomato(vector<XYZ> _xyz) {

	vector<XYZ> firebe = {};
	for (auto a : _xyz) {
		for (auto Dir : MoverDirection) {
			int  xyz2[2] = { get<0>(a) + get<0>(Dir),get<1>(a) + get<1>(Dir) };

			if (!(get<0>(a) + get<0>(Dir) < N && get<0>(a) + get<0>(Dir) >= 0 &&
				get<1>(a) + get<1>(Dir) < H && get<1>(a) + get<1>(Dir) >= 0)) {
				continue;
			}

			if (vec[xyz2[0]][xyz2[1]] == 0) {
				firebe.push_back(XYZ(xyz2[0], xyz2[1]));
				vec[xyz2[0]][xyz2[1]] = 1;
			}
		}
	}
    //익은것들 위치반환
	return firebe;
}


int main() {


	cin >> H >> N ;

	vector<XYZ> fire;
	int answer = 0;
	for (int i = 0; i < N; i++) {
		vec.push_back({});
		for (int j = 0; j < H; j++)
		{
			int a;
			cin >> a;
			vec[i].push_back(a);

			if (a == 1)
			{
				fire.push_back(XYZ(i, j));
			}
			if (a == 0) {
				nonfire.push_back(XYZ(i, j));
			}

		}
	}

	while (true)
	{
    
		if (fire.size() <= 0)
			break;
		//다음으로 익을 토마토 구하기
        fire = findNextTomato(fire);
		
        //일자 업데이트 
		answer++;
	}
    
	for (auto a : nonfire) {
		if (vec[get<0>(a)][get<1>(a)] == 0)answer = 0;
	}
	cout << (answer - 1);

}

익은 위치와 익지않은 위치를 받아준뒤

}

while{

       func (익은 토마토들) 

             return이제 익은 토마토 위치 반환

        반복하며 answer+1

}

}

위와 같은 행위를  결국 익을게 없을때 까지 반복한다.

더이상 익을게 없을때

안익었던 토마토들이 아직도 익지않았는지 확인한다.

매우 쉬운코드 

예전에 짠코드여서 왜 그랬는지 모르겠지만 queue를 써봤다가 안쓰고 vector로 풀어보려고 풀어보았던거 같다.

queue로 BFS를 풀고 얕은복사를 좀더 활용하는게 좋을거같다.

만약 시각적으로 보면서 확인해야 이해하기 쉬울거 같다 생각한다면! 

	while (true)
	{
		if (fire.size() <= 0)
			break;
		fire = findNextTomato(fire);

		//cout << endl;

		for (auto x : vec) {
			for (auto y : x) {
				cout << y;
				cout << " ";
			}
			cout << endl;

		}

		answer++;
	}

를 추가해서 점점 퍼지는걸 볼수있따 :-)

https://www.acmicpc.net/problem/15806

통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검사에서 나쁜 점수를 받으면 벌점을 받게 되고, 벌점이 많이 쌓이면 기숙사에서 퇴사 해야 한다. 영우는 어떤 경우에 벌점을 받는지 궁금하여 기숙사에서 진행하는 청소 검사 시스템에 대해 자세히 조사해 보았다. 기숙사 청소 검사 시스템은 오늘로부터 정확히 t 일이 지나고 검사를 하며, 검사 시간 단축을 위해 방의 특정 부분만 검사한다. 하지만 검사하는 특정 부분 중 한 곳이라도 더럽다면 영우는 벌점을 받게 된다. 영우가 사는 방은 N * N 정사각형 방이며, 기숙사 방바닥에는 곰팡이가 서식하고 있다. 곰팡이는 1 일이 지날 때마다 특이한 방식으로 증식하는데, 그림 1(a)의 곰팡이는 1 일이 지나면 그림 1(b)와 같이 8 군데로 증식되고, 원래의 곰팡이는 사라진다. 만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다. 그림 2 는 두 군데의 곰팡이가 1 일이 지난 후 모습이다.

위 그림은 증식방식이다.

해당문제는 처음 보았을때 단순 시물레이션 문제와 같다고 생각할수 있지만

그냥 구현하게 된다면  반복적인 처리로인해 계산해야 하는 곰팡이가 기하급수적으로 늘어난다

해당 문제를 잘 생각해본다면 최적화 할수있는 부분이 쉽게 보인다.

중앙에서 시작할경우 퍼지는 모습은 아래와 같다

위 이미지로 알수있는것은  이동 했던 칸에서 다시 원래자리에 곰팡이를 복구 시킨다는 사실이다.

그렇다면 해당 위치에 곰팡이가 생기고 하나라도 이동했을경우엔 무한정 곰팡이가 번식한다는 이야기다...으...

그렇다면 두번째로 생각할수있는것은 

해당 위치에서 1턴 쉬면서 반복한다 라는것은 

홀수날과 짝수날을 구분지어 두개의 영우의방을 돌아가면 계산한다면,

해당 위치가 이미 곰팡이가 있었던 적이 있었는지도 간단하게 체크할수있다.

BFS를 사용해서 반복체크를 할때 다음 날의 위치가 일전에 도달한적 있는 위치라면

이미 반복했던 위치기에 다시 곰팡이를 그릴 이유가 없다.

하지만 해당 문제는 쉽게 지나칠수 있는 문제가 존재한다.

바로 마지막줄인 "만약 곰팡이가 증식해야 하는 부분이 벽으로 막혀 있다면, 그곳으로는 증식하지 못한다."

해당 문제에서 증식 하지못한다면 자연적으로 사라진다.

곰곰히 생각해보면 3*3의 가운데 지점 에서만 문제가 될수있다.

그 미만(2*2 ,1*1)에서는 곰팡이는 생존이 불가능하고

초과되었을때는 어느 장소에 생겨도 한무반복은 예정되어있다.

예외 예제를 보자 

해당위치는 3*3이상에서 의 유일한 사라지는 위치다. 이부분만 조심해서 문제를 풀자.

프로그램의 입력은 표준 입력으로 받는다. 첫 줄에 영우의 방의 크기, 방에 있는 곰팡이의 개수, 청소 검사 시스템이 검사하는 방바닥 좌표의 개수, 청소 검사가 실시 되기까지 남은 일수인 N M K t 가 주어진다.

(1 ≤ N ≤ 300, 0 ≤ M ≤ N2, 0 ≤ K ≤ N2, 1 ≤ t ≤ 10000)

둘째 줄부터 M 개의 줄에 걸쳐 영우의 방에 있는 곰팡이의 위치인 Mx My가 주어진다.(1 ≤ Mx, My ≤ N)

다음 줄부터 K 개의 줄에 걸쳐 검사관이 검사하는 방바닥의 위치인 Kx Ky가 주어진다.(1 ≤ Kx, Ky ≤ N)

N 영우의 방크기

M 방에있는 곰팡이의 개수

K 검사하는 방바닥 좌표의개수

t  청소 검사가 실시 되기까지 남은 일수

5 2 4 1

2 1

3 3

3 1

3 2

3 3

3 4

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void ClearRoom() {

	int N, M, K, t;
	cin >> N >> M >> K >> t;
	std::vector<vector<bool>> vmap(N + 1, vector<bool>(N + 1, false)),
		avmap(N + 1, vector<bool>(N + 1, false)),
		* Nextpm, * Dpm;
	std::queue <int> QSearchX;
	std::queue <int> QSearchY;


	int x = 0, y = 0;
	for (int i = 0; i < M; i++)
	{
		cin >> x >> y;
		vmap[--x][--y] = true;
		QSearchX.push(x);
		QSearchY.push(y);
	}

	const int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
	const int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
	for (int i = 0; i < t; ++i) {

		int Qsize = QSearchX.size();
        
        //오늘 방과 내일 영우의 방
		Dpm = &(((i % 2) != 0) ? avmap : vmap);
		Nextpm = &(((i % 2) == 0) ? avmap : vmap);
		//현재 일수에 움직이는 곰팡이
        for (int j = 0; j < Qsize; j++)
		{
			int datax = QSearchX.front();
			int datay = QSearchY.front();
			QSearchX.pop();
			QSearchY.pop();
			bool check = false;
            
            //8방향 곰팡이 번식
			for (int i = 0; i < 8; ++i) {
				x = datax + dx[i];
				y = datay + dy[i];
				
                //곰팡이 가 번식 가능한지 확인후 번식
                if ((x < N && x >= 0 && y < N && y >= 0) && !(*Nextpm)[x][y])
				{
                	(*Nextpm)[x][y] = true;
                    // 다음 번식 예정인 queue
					QSearchX.push(x);
					QSearchY.push(y);
					check = true;
				}
			}
            //만약 해당 곰팡이가 어느 하나도 이동하지 못햇더라면
            //이 곰팡이는 다음날 죽는다.
			if (!check) {
				(*Dpm)[datax][datay] = false;
			}
		}
	}
	bool IsClear = false;
	Dpm = &(((t % 2) != 0) ? avmap : vmap);
    
    //검수의 날
	for (int i = 0; i < K; i++)
	{
		cin >> x >> y;
		if ((*Dpm)[x-1][y-1])IsClear = true;
		if (IsClear)break;
	}
	cout << (IsClear ? "YES" : "NO");
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	ClearRoom();
}

해당 문제를 풀며 

배열 문제의 1입력 과 0입력을 확실하게 잡아야했고

 또한 문제 t의 정의에 대해 확실하게 잡아야했다.

아래 시뮬레이터로 문제의 경우의 수를 확인해보자

영우가 빠른시일 내로 청소하지 않는다면 집은 곰팡이에게 잠식당해 버릴지도 모른다.

부분합은 특정 구간의 합을 효율적으로 계산하기 위해 누적합을 활용하는 방법이다.

입력할때 전부 더해두고 이후에 재사용한다는 계념이다.

그래서 최소 한번이상 사용해야 이득이다.

1차원배열은 

 index = [1]   [2]    [3]   [4]    [5]      [6] 이 있다

 DP =    [1]   [3]    [6]   [10]   [15]   [21] 배열을 만들어준뒤

배열은 이전값에서 M을 더한 값   [N]= [N-1] + M

3번부터5번값 을 구해야 한다면?

아래처럼 3 부터 5까지 index를 하나씩 올리며 구해도 괜찮다. 

 [1]   [2]   [3]   [4]    [5]      [6]

 1      2     3     4      5        6

                3      4     5

                       12

DP 배열 에서 구하는법은 아래와 같다

우선 쉽게 위치로 보자면  

1       3       6 10 15       21

1       2       3~~~5`

포함되어있지않은 x-1 를 찾아준다

            [3]     [6]     [15]
          [x-1]              [ y]

비포함인부분을 포함되어있는 부분에서 빼주면 

            [y]  -  [x-1] 

           15  - 3    =   12

2차원행렬은 

기본적인 아이디어가 똑같기에 더해준뒤 중복값 제거 

그렇다면 x1,y1   x2, y2 를 계산할땐 어떤식으로 계산해야할까

위와 같은 행렬 에서 해당파란  0,0   1,1  부분을 구하고싶다면

그냥 1,1 부분을 출력해도 무방할것이다.

그렇다면

같은 부분을 구하려면 어떻게 해야할까

이것도 1차원 행렬 과 같은방식이다.

아래는 DP 행열이다

우선 전체 합인 22  

그리고 제외할부분인 6 과 6 을 빼준다

그러면 6에는공통적으로 들어가게 되는 1이 두번 빠지게 된다.

그럼으로 공통적으로 빠지는 1을 더해주면  구역값이 나오게 된다.

22 - 6 - 6 +1

이걸 펼쳐본다면

전체 크기에 빠진크기만큼 세로 가로를 빼준뒤 중복되어있는부분을 다시 더해주면 완성!

행렬  옆 0 줄이 있는건 계산을 쉽게 하기 위해서다.

아래 구현 코드와 계산기로 쉽게 확인해보자

	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);


	int N, M;
	cin >> N >> M;
	int mix_n = N, mix_m = N;
	vector<vector<int>> vmap(mix_n + 1, vector<int>(mix_m + 1, 0));
	for (int i = 1; i < mix_n + 1; i++)
	{
		for (int j = 1; j < mix_m + 1; j++)
		{
			int k = 0;
			cin >> k;
			vmap[i][j] = k + vmap[i - 1][j] + vmap[i][j - 1] - vmap[i - 1][j - 1];
		}
	}
	for (int i = 0; i < M; i++) {
		int Lx, Ly, Rx, Ry;
		cin >> Lx >> Ly >> Rx >> Ry;
		int mixAnswer = vmap[Lx - 1][Ly - 1] + vmap[Rx][Ry] - vmap[Rx ][Ly - 1] - vmap[Lx - 1][Ry ];
		cout << mixAnswer<<"\n";
	}

유니티에는 단축키를 쉽게 확인하고 단축키를 지정할수 있는 기능이 있다.

게임엔진 답게 다른 프로그램보다 확인하기 쉽게 되어있다.

너무 간단한 기능이기에 이런게 있구나 하고  어떤 단축키들이 할당되어있는지 보고 넘어가도 좋다.

한번 보도록 하자.

우선 Shortcuts을 키는 법은 Edit -> Shortcuts.. 에서 확인할수 있다.

누르면 창이 하나 켜진다.

아래와 같은 창이 켜지는 것을 확인할수있다.

키에 마우스를 올리면 어떠한 단축키가 할당되어있는지 확인할수있다.

색마다 다른데

유니티에는 단축키를 쉽게 확인하고 단축키를 지정할수 있는 기능이 있다.

게임엔진 답게 다른 프로그램보다 확인하기 쉽게 되어있다.

한번 보도록 하자.

우선 쇼우올컷 을 키는 법은 Edit -> Shortcuts..

아래와 같은 창이 켜지는 것을 확인할수있다.

초록색 네모칸은 현재 할당되어 있는 키를 확인할수있는데.

마우스를 올리면 어떤 기능이 할당되어있는지 알수있다.

설명이 버전마다 살짝식 차이가 있는데.

우선 유니티 공식 문서에선 아래와 같이 설명하고있다.

하지만  직접 캡쳐한 버전에선

위에 설명으로 

보라색 키 역시 mixed key 로 색이 다르게 추가되어있다.

마우스를 올리고 기다리면 할당되어있는 단축키를 보여준다

우클릭시

지우거나 기본설정으로 초기화 할수있으며

특수키 를 키보드로 누르거나 마우스로 누르면 

연계되어있는 숏컷만 확인도 가능하다.

또한 단축키 세팅을 새로만들거나 저장, 불러오기 가 가능하다.  

마지막으로 아래와 같이  숏컷의 종류들을 전부 확인가능하다.

할당안되어있는 것들은 눌러서 단축키를 넣어줄수있다.

아래와같이  맨오른쪽의 숏컷 부분을 누른뒤 원하는 키를 눌렀다 때면 생성할수있고.

사용할수있다.

여기서도 우클릭하면 초기화 제거 를 할수있다.

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

BFS와 DFS 문제 레벨3 단계의 여행경로 문제다.

이해하는 데 확실히 오래 걸린 문제다



처음 생각은 그냥 DFS 문제인 줄 알고 알파벳 정렬 후 빠른 순으로 탐색하였다.
풀면 채점 시 1번 2번 실패, 3번 4번 성공한다.



생각해 낸 아이디어는
위 문구처럼 무조건 다 갈 수 있다는 이야기는


만약 끝까지 탐색 DFS를 했을 경우에도 모든 티켓(간선)을 사용하지 않았다면 그 간선은 마지막에 방문해야 하는 간선이다.


또한 같은 티켓이 두 개일 수 있다.





1. 그래프를 만들며 그래프를 알파벳순으로 정렬한다.
2. 그래프를 순서대로 탐색한다.
3. 더 이상 다른 노드로 이동할 수 없는 경우 사용한 티켓(간선)의 개수와 전체 티켓(간선)의 개수를 체크한다.
3.1달을 경우 이전 노드로 돌아간다.
4 만약 돌아왔으면 다음 2로 돌아가 다음 순서 노드를 탐색한다.

#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int ticketSize = 0;
vector<string>Aanswer;
bool findAir(string start,int num,vector<string> answer, map<string, map<string, int>, greater<string>>ticketsmap) {


    //사용한 티켓 기록
    answer.push_back(s.first);

   //이동한 간선수와 전체 간선의 수 비교
    if (num == ticketSize) { Aanswer = answer; return true; }

   //정렬된 간선 순서대로 이동
    for (auto s : ticketsmap[start]) {

    //간선이 존재하는가 확인
        if (s.second >0) {
        // 티켓 갯수 빼기
            ticketsmap[start][s.first]--;
            //재귀함수 실행 
            if (findAir(s.first, num + 1, answer, ticketsmap) == true) 
            {
                //true 반환시 탈출
                return true; 
            }
            else {
                //만약 현재 티켓대로 갔을경우 전부 소진하지 못할경우
                //티켓을 사용하지 않은 상태로 원복 시킨다
                ticketsmap[start][s.first]++;
            }
        }
    }

    //간선을 전부 돌았지만 티켓을 전부 사용하지 못했을경우 false 반환
    answer.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {

    string start = "ICN";
    map<string, map<string, int>> ticketsmap;
    for (int i = 0; i < tickets.size(); ++i)
    {
    //티켓 그래프 제작
        ticketsmap[tickets[i][0]][tickets[i][1]]++;
        ticketSize += 1;
    }
    vector<string> answer = {};

    findAir(start,0, answer, ticketsmap);

    return Aanswer;
}

아래와 같이 확인할수 있다