TIL day 67

1. 코딩테스트

---

오늘은 BFS, DFS관련 수업을 듣고, 프로그래머스 level 3 - 여행경로 문제를 풀었습니다.

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

프로그래머스

 

내가 풀었던 생각의 흐름 (이 방식으로 해결 못함)

• string을 넣었을때 string들을 출력해줘야 하니까 컨테이너는 unordered_map<string, vector<string>> 으로 구성했다.
• 이후 방문 표시를 해주기 위해서 vis라는 컨테이너를 두었는데, 출발지와 도착지를 모두 포함해야 하니까 두 문자열을 합쳐서 저장하는 unordered_map<string, int> vis 로 구성했다.
  • 이 컨테이너는 또한 중복을 포함할 수도 있기 때문에 0보다큰 경우 방문할 수 있도록 구성했다.
• 이후 BFS를 돌면서, 방문한 경우는 continue하고 방문되지 않은 경우는 queue에 push 해주었다.
• 근데, 이때 만약 끝까지 갈 수 없는 경우가 있다면 해당 장소를 방문하지 않고, 다른 장소를 방문해야 하는 것이 포인트였다.
  • 예를 들어, abcd 네개의 vertex가 존재하고 다음과 같은 edge가 주어질 때 (a->c), (c->d), (d->b) ,(c->b)
  • a->c->d->b 로 가면 모두 돌 수 있지만,
  • a->c->b 로 가면 모든 티켓을 다 쓰지 못하게 된다.
  • 이러한 처리를 위해 for문을 통해서 다음으로 들어갈 값에 대해서 체크를 했지만, 이것 역시 다음 단계에 대해서만 체크를 하는 것이고 두단계 이후의 값에 대해서는 제대로 처리를 하지 못하게 된다.
  • (여기서 뭔가 백트래킹을 써야하나 라는 생각이 들기도 했다. 왜냐면 가보고 안되면 다시 돌아오는 그런 느낌이니)
• 결론 : BFS가 아니라 DFS를 통해 풀어야 한다.
  
  • 인터넷을 참고해서 백트래킹과 유사하게 푼 풀이를 보고 공부를 했다.
  • 백트래킹이랑 DFS는 유사성이 있는 것 같아서 좀 더 관련 문제를 풀어봐야 할 것 같다는 생각이 들었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<string>> ticket;
vector<string> answer;
bool vis[10002];
bool isAnswer;

void DFS(string cur, int cnt)
{
	answer.push_back(cur);

	//모든 티켓을 다 쓴 상황
	if (cnt == ticket.size())
	{
		isAnswer = true;
	}

	for (int i = 0; i < ticket.size(); ++i)
	{
		if (vis[i])
			continue;
		if (ticket[i][0] == cur)
		{
			vis[i] = true;
			DFS(ticket[i][1], cnt + 1);

			if (!isAnswer)
			{
				answer.pop_back();
				vis[i] = false;
			}
		}
	}

}

vector<string>solution(vector<vector<string>>tickets)
{
	sort(tickets.begin(), tickets.end());
	ticket = tickets;
	DFS("ICN", 0);

	return answer;
}

 

 

 

2. 언리얼 멀티플레이

---

오늘 데디케이트 서버로 야구 게임을 만드는 강의를 들었습니다. (과제 해설 강의)

근데 뭔가 깨우친듯한 느낌이 들었고, 그전까지 이해가 안되던 것들이 왜 그런지 이해가 되는 느낌....

(내가 과제로 만든 야구 게임은 멀티 게임으로 적합한 로직이 아니었던 것 같습니다..)

 

강의 다시 듣고 따라하면서 관련 내용을 정리해보고 익숙해져야할 것 같습니다.

 

특히 언리얼의 "게임플레이 프레임워크를 이렇게 쓰는거다" 라는 것을 느낀 것 같았습니다.

 

추후 관련 글을 정리해서 올릴 예정입니다.

진짜 정리할 것임

 

 

3. 언리얼 과제 

---

언리얼 커스텀 플러그인을 만드는 과제가 있어서, 빠르게 완료를 했습니다.

 

플러그인 빌드순서랑, 블루프린트 펑션 라이브러리가 아직 익숙하지 않아 조금 시간이 걸렸지만 해결하였고 관련 글을 정리하였습니다.

https://gbleem.tistory.com/138

Unreal Engine - 플러그인 만들기

 

추가적으로 블루프린트 펑션 라이브러리를 사용하다가 static에 대한 내용이 궁금해서 관련 내용을 공부해 보았습니다.

https://gbleem.tistory.com/139

static Keyword