TIL day 55

1. 코딩 테스트

---

오늘 오전에는 그래프 관련 공부를 진행하였습니다.

 

그래프 관련 문제들 중에서 bfs 관련 문제는 많이 풀어봐서 익숙했지만, dfs 관련 내용이 부족하다고 느껴져서 해당 부분 공부를 집중적으로 진행하고 관련 내용을 정리해 보았습니다.

 

특히, 비재귀 형태로 구현한 dfs를 올바를 순서로 탐색하도록 하는 방식을 잘 기억해야할 것 같습니다. 

 

https://gbleem.tistory.com/117

그래프 (재귀, 비재귀 DFS)

 

추가로 백준에서 관련 문제를 하나 풀었습니다.

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

실버1 문제 - 케빈 베이컨의 6단계 법칙

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

int n, m;
vector<int> adj[102];
int vis[102];
vector<pair<int, int>> answer;

void bfs(int cur)
{
	fill(vis, vis + n + 2, -1);
	queue<int> q;
	q.push(cur);
	vis[cur] = 0;

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

		for (int nxt : adj[cur])
		{
			if (vis[nxt] == -1)
			{
				q.push(nxt);
				vis[nxt] = vis[cur] + 1;
			}
		}
	}

	int temp = 0;
	for (int i = 1; i <= n; ++i)
	{
		temp += vis[i];
	}
	answer.push_back({ temp, cur });
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int i = 1; i <= n; ++i)
	{
		bfs(i);
	}
	int minValue = INT_MAX;
	for (auto a : answer)
	{
		minValue = min(minValue, a.first);
	}
	int result = INT_MAX;
	for (auto a : answer)
	{
		if (a.first == minValue)
		{
			result = min(result, a.second);
		}
	}

	cout << result;
 }

 

 

2. 언리얼 강의 시청

---

언리얼 멀티플레이 관련 강의를 시청하였습니다.