TIL day 85

1. 코딩테스트

---

백준 클래스 4의 알파벳 문제

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

• 처음 풀이
  • bfs로 찾을 것인데, 특이점은 선택한 경로로 이동하는 동안에 방문 배열을 유지해야 한다.
  • 예를 들어, CAAB /n ADCB 라는 char 배열이 주어졌을 때
    • C -> A -> D 로 가는 경로가 있다면, 이 "해당 경로에만 유지되는" 방문체크 배열이 필요하다.
    • 그 이유는 bfs 방문하는 순서가 인접한 것들부터 방문하고 퍼져 나가는 순서인데, 이렇게 되면 오른쪽으로 방문하는(y가 커지는) 경로와 아래로 방문하는(x가 커지는) 경로에 둘 다 A가 있으므로 만약 오른쪽으로 먼저 진행했다면, 아래로는 방문을 못하는 경우가 생긴다. (이미 A는 방문체크를 해버리니까)
  •  그래서 해결책으로 queue 자체에 string 경로를 저장해 두어 진행하였으나, 시간 초과가 발생했다. (아마도 string 에서 char를 찾는 find 함수 때문일 것)

#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <unordered_map>
using namespace std;

int r, c;
char board[22][22];
int answer = 0;
unordered_map<string, int> um;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> r >> c;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin >> board[i][j];
		}
	}
	queue<tuple<int, int, string>> q;
	string str = "";
	str += board[0][0];	
	q.push({ 0,0, str });
	um[str] = 1;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; ++dir)
		{
			int nx = get<0>(cur) + dx[dir];
			int ny = get<1>(cur) + dy[dir];
		
			//범위 벗어남
			if (nx < 0 || nx >= r || ny < 0 || ny >= c)
				continue;
			string temp = get<2>(cur);

			//중복된 알파벳
			if (temp.find(board[nx][ny]) != string::npos)
				continue;
			
			q.push({ nx, ny, temp + board[nx][ny] });
			um[temp + board[nx][ny]] = um[temp] + 1;
		}
	}

	for (const auto& u : um)
	{
		answer = max(answer, u.second);
	}

	cout << answer;
}

• 다음 풀이
  • 사실 최단 경로 문제는 아니니까 dfs를 생각하는 것이 좋은 선택이었다. (bfs가 익숙하다고 이것만 고집하지 말기)
  • 또한, 잘 생각해보면 백트래킹식 선택과정이 있으므로 (일단 가보고 안되면, 다시 다 돌아와서 다시 가는 느낌) dfs와 백트래킹 연결하여 푸는 것이 베스트 방법이었다.
  • 주의점
    • 그러나 처음에 풀때 방문 체크를 unordered_map<char, int> 로 진행했지만, 이 방식 또한 시간초과가 발생했다.
      
      • 배열이나 unordered_map이나 O(1) 로 찾는 것이라 생각했지만, 아무래도 해시가 더 오버헤드가 있는 작업이기 때문인 것 같다.
      • 특히 알파벳은 26개 밖에 없기 때문에 간단하게 배열을 써서 해결이 가능하다. (기억해 둘 방식)
  • 정답 코드

#include <iostream>
#include <unordered_map>
using namespace std;

int r, c;
char board[22][22];
char vis[28];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int answer = 0;

void dfs(int x, int y, int cnt)
{
	answer = max(answer, cnt);

	for (int dir = 0; dir < 4; ++dir)
	{
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if (nx < 0 || nx >= r || ny < 0 || ny >= c)
			continue;

		if (!vis[board[nx][ny] ])
		{
			vis[board[nx][ny]-'A'] = 1;
			dfs(nx, ny, cnt + 1);
			vis[board[nx][ny]-'A'] = 0;
		}

	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c;

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin >> board[i][j];
		}
	}
	
	vis[board[0][0] - 'A'] = 1;
	dfs(0, 0, 1);

	cout << answer;
}

 

 

2. 언리얼 

---

팀 프로젝트를 진행하면서 만든 멀티플레이 미니게임을 구현하면서 겪었던 문제들과 기억할 만한 내용들을 정리해 보았습니다.

https://gbleem.tistory.com/163

UE5 Issues - 리슨 서버 게임 이슈들