언제나 처음처럼

[문제 링크]

최소 스패닝 트리를 구하는 알고리즘인 크루스칼 알고리즘을 사용하여 간단히 풀 수 있는 문제였다.

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

class OptimizedDisjoinSet {
	vector<int> parent, rank;

public:
	OptimizedDisjoinSet(int n) : parent(n), rank(n, 1)
	{
		for (int i = 0; i < n; i++)
			parent[i] = i;
	}

	int find(int u)
	{
		if (u == parent[u]) return u; //자기 자신을 가리키면 뿌리노드임
		return parent[u] = find(parent[u]); // 위에 부모노드가 있다면 재귀호출
	}

	void merge(int u, int v)
	{
		u = find(u); v = find(v);
		if (u == v) return; // 뿌리노드가 서로 같다면 걸러낸다

		// rank[u]의 높이가 더 높다면 rank[u]랑 rank[v]를 바꾼다
		if (rank[u] > rank[v]) swap(u, v);

		// 이제 무조건 rank[u]의 높이가 더 낮으므로 u를 v의 자식으로 넣는다
		parent[u] = v;

		// rank[u]와 rank[v]의 높이가 같다면 rank[v] 높이를 1 증가시킨다.
		if (rank[u] == rank[v]) ++rank[v];
	}
};

const int MAX_V = 10001;
int V, E;
vector<pair<int, int>> adj[MAX_V];

int kruskal()
{
	vector<pair<int, pair<int, int>>> edges;
	for (int u = 1; u <= V; u++)
		for (int i = 0; i < adj[u].size(); i++)
		{
			int v = adj[u][i].first;
			int cost = adj[u][i].second;

			edges.push_back({ cost, {u, v} });
		}

	sort(edges.begin(), edges.end());

	OptimizedDisjoinSet sets(V+1);
	int ret = 0;

	for (int i = 0; i < edges.size(); i++)
	{
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;

		if (sets.find(u) == sets.find(v)) continue;

		sets.merge(u, v);
		ret += cost;
	}

	return ret;
}

int main(void) {
	cin >> V >> E;

	for (int i = 0; i < E; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		adj[A].push_back({ B, C });
	}

	cout << kruskal() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day

[문제 링크]

입력으로 키를 비교한 두 학생이 주어지고 그 학생들끼리는 명확한 순서가 존재하기 때문에 위상정렬을 통해 풀 수 있는 문제였다.

학생들의 키 관계 그래프를 인접행렬로 표현했을 때 메모리초과가 되기 때문에 인접리스트로 구현하였다.

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

bool seen[32001];
vector<int> order;
vector<int> adj[32001];
int N, M;

void dfs(int here) {
	seen[here] = true;
	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];
		if (!seen[there]) dfs(there);
	}

	order.push_back(here);
}

vector<int> topologicalSort() {
	for (int i = 1; i <= N; i++)
		if (!seen[i]) dfs(i);

	reverse(order.begin(), order.end());

	return order;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		adj[A].push_back(B);
	}

	vector<int> result = topologicalSort();

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << ' ';

	return 0;
}

알고리즘 200일 프로젝트 - 164 day

[문제 링크]

너비 우선 탐색을 공부하기 전에 한번 풀어봤던 문제였다. 그때는 몇시간을 고민해도 결국 시간초과의 늪에서 빠져나오지 못했었는데 너비 우선 탐색으로 접근하니까 어렵지 않게 풀 수 있었다.

입력받는 단계에서 R, B, O 의 위치를 미리 저장한 다음, R의 위치와 B의 위치를 queue에 담고 너비 우선 탐색을 시작한다.

기울였을 때 앞에 있는 볼보다 뒤에 있는 볼이 먼저 움직이는 상황을 방지하기 위해 기울이는 방향에 따라 더 앞에 있는 볼 먼저 움직이도록 구현하였다.

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

struct Pos {
	int y;
	int x;

	bool operator== (const Pos& rhs)
	{
		if (y == rhs.y && x == rhs.x) 
			return true;
		else 
			return false;
	}
};

Pos R, B, O;
char board[10][10];
int N, M;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void Move_R(Pos& thereR, const Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereR.y + dy[type], thereR.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereR = next;
			break;
		}
		else if (next == thereB) {
			break;
		}
		else {
			thereR = next;
		}
	}
}

void Move_B(const Pos& thereR, Pos& thereB, int type)
{
	while (1) {
		Pos next = { thereB.y + dy[type], thereB.x + dx[type] };

		if (board[next.y][next.x] == '#') break;
		if (board[next.y][next.x] == 'O') {
			thereB = next;
			break;
		}
		else if (next == thereR) {
			break;
		}
		else {
			thereB = next;
		}
	}
}

void MovingBall(Pos& thereR, Pos& thereB, int type)
{
	if (type == 0) { // 좌로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x > thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 1) { // 우로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.y == thereB.y && thereR.x < thereB.x) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}

	else if (type == 2) { // 아래로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y > thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}


	else if (type == 3) { // 위로 이동
		// 이동 방향 기준으로 R이 앞에 있는 경우
		if (thereR.x == thereB.x && thereR.y < thereB.y) {
			// R 먼저
			Move_R(thereR, thereB, type);
			Move_B(thereR, thereB, type);
		}
		else {
			// B 먼저
			Move_B(thereR, thereB, type);
			Move_R(thereR, thereB, type);
		}
	}
}

int bfs()
{
	queue<pair<pair<Pos, Pos>, int>> q;
	q.push({ { R, B }, 0 });

	while (!q.empty())
	{
		Pos hereR = q.front().first.first;
		Pos hereB = q.front().first.second;
		int move = q.front().second;

		q.pop();

		// 이동횟수 10회 초과 시 불가능
		if (move > 10) break;

		// R or B 가 구멍에 들어갔을 경우
		if (O == hereR || O == hereB)
		{
			if (O == hereB) // B가 구멍에 빠지면 실패 
				continue;
			else			// R만 구멍에 빠지면 성공
				return move;
		}

		for (int i = 0; i < 4; i++)
		{
			Pos thereR = hereR;
			Pos thereB = hereB;
			MovingBall(thereR, thereB, i);
			
			// 두 공다 움직이지 않았다면 건너뜀
			if (thereR == hereR && thereB == hereB) continue;

			q.push({ {thereR, thereB}, move + 1 });
		}
	}

	return -1;
}

int main(void)
{
	cin >> N >> M;

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> board[i][j];

			if (board[i][j] == 'R')
				R = { i,j };
			else if (board[i][j] == 'B')
				B = { i,j };
			else if (board[i][j] == 'O')
				O = { i,j };
		}

	cout << bfs() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day

[문제 링크]

한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였다.

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

const int INF = 987654321;
int V, E;
vector<pair<int, int>> adj[20001];

vector<int> dijkstra(int start)
{
	vector<int> dist(V+1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;
		
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;

			if (dist[there] > nextDist)
			{
				dist[there] = nextDist;
				pq.push({ -nextDist, there });
			}
		}
	}

	return dist;
}

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

	cin >> V >> E;

	int start;
	cin >> start;

	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;

		adj[u].push_back({ v,w });
	}

	vector<int> result = dijkstra(start);

	for (int i = 1; i <= V; i++)
	{
		if (result[i] == INF)
			cout << "INF" << '\n';
		else
			cout << result[i] << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 163 day

[문제 링크]

현재 좌표에서 동서남북 방향을 깊이 우선 탐색 함으로써 한 단지에 속하는 좌표를 방문하고 집의 개수를 저장하였다.

그리고 한번 깊이 우선 탐색을 했는데 방문하지 않은 좌표가 존재한다면 또다른 단지가 존재하는 것이므로 그 좌표를 시작으로 다시 깊이 우선 탐색 하는 것을 반복하도록 구현하였다.

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

int N;
vector<string> board(25);
bool visited[25][25];

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

struct Pos 
{
	int y;
	int x;
};

int dfs(Pos here)
{
	int ret = 1;

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

		if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			if (!visited[ny][nx] && board[ny][nx] == '1')
			{
				visited[ny][nx] = true;
				ret += dfs({ ny, nx });
			}
	}

	return ret;
}

int main(void) 
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> board[i];

	vector<int> result;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			if (!visited[i][j] && board[i][j] == '1')
			{
				visited[i][j] = true;
				Pos start = { i,j };
				result.push_back(dfs(start));
			}

	sort(result.begin(), result.end());

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day

[문제 링크]

(0, 0) 위치에서 시작하여 동 서 남 북 방향을 확인하면서 이동 가능한 방향에 아직 방문하지 않고 값이 '1'인 위치가 있다면 queue에 추가해주는 너비 우선 탐색으로 구현하였다.

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

int N, M;
vector<string> board(100);
bool discovered[100][100];

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

struct Point
{
	int y;
	int x;

	Point(int _y = 0, int _x = 0) : y(_y), x(_x) { }

	bool operator== (const Point& rhs) {
		if (y == rhs.y && x == rhs.x) return true;
		return false;
	}
};

int bfs() {
	queue<pair<Point, int>> q;
	q.push({ {0,0},1 });
	discovered[0][0] = true;

	Point target = { N - 1, M - 1 };

	while (!q.empty()) {
		Point here = q.front().first;
		int move = q.front().second;

		q.pop();

		if (target == here)
			return move;

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

			if (ny < N && ny >= 0 && nx < M && nx >= 0)
				if (!discovered[ny][nx] && board[ny][nx] == '1') {
					discovered[ny][nx] = true;
					q.push({ { ny, nx }, move + 1 });
				}
		}
	}

	return -1;
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> board[i];

	cout << bfs() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day

[문제 링크]

트라이 자료구조를 사용하여 문자열을 빠르게 검색하는 문제인데 여러가지 고려해줘야할 것이 많아서 어려웠던 문제였다.

먼저 trie 객체에 count 변수를 추가하고 words 문자열이 각 노드를 방문하는 횟수를 카운팅함으로써 해당 위치에서 '?' 를 만났을 경우 가능한 가지수를 탐색하지 않고 바로 반환받을 수 있도록 하였다.

"????o" 와 같이 '?'가 접두사로 등장하는 경우에는 queries를 역순으로 탐색 해줘야하기 때문에 words를 뒤집은 문자열을 가지고 새로운 trie를 한개 더 만들었다.

마지막으로 '?'까지 문자열은 일치하지만 길이가 다른 경우를 걸러주기 위해 trie 객체를 words와 queries의 최대 길이인 10000만큼의 크기를 가진 배열로 선언하여 길이에 따라 다른 트라이에 담아주었다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	if (ch == '?') return ALPHABETS;
	
	return ch - 'a'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int count;
	bool terminal;

	TrieNode() : terminal(false), count(1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here)
	{
		if (here == key.size()) terminal = true;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();
			else
				children[next]->count++;

			children[next]->insert(key, here + 1);
		}
	}

	int find(string& key, int here)
	{
		if (here == key.size()) return this->terminal ? 1 : 0;

		int next = toNumber(key[here]);

		int cnt = 0;

		if (next == ALPHABETS)
		{
			for (int i = 0; i < ALPHABETS; i++)
				if (children[i] != NULL)
					cnt += children[i]->count;
		}
		else
		{
			if (children[next] == NULL) return 0;
			else
			{
				cnt = children[next]->find(key, here + 1);
			}
		}

		return cnt;
	}
};

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;

	vector<TrieNode> word(10001);
	vector<TrieNode> reword(10001);

	for (int i = 0; i < words.size(); i++)
	{
		int len = words[i].size();

		word[len].insert(words[i], 0);

		reverse(words[i].begin(), words[i].end());
		
		reword[len].insert(words[i], 0);
	}

	for (int i = 0; i < queries.size(); i++)
	{
		int len = queries[i].size();

		if(queries[i][0] != '?')
			answer.push_back(word[len].find(queries[i], 0));
		else
		{
			reverse(queries[i].begin(), queries[i].end());
			answer.push_back(reword[len].find(queries[i], 0));
		}
	}
	return answer;
}

알고리즘 200일 프로젝트 - 144 day

[문제 링크]

이 문제와 같이 많은 양의 문자열을 검색하는 요구하는 문제들은 트라이 자료구조를 활용하면 효율적으로 해결할 수 있다.

트라이 자료구조는 알고리즘 문제해결 전략에서 구현한 것과 똑같이 구현하였다.

사전에 포함된 단어들을 출현 빈도에 따라 내림차순으로 정렬하고 출현 빈도가 같을 경우 오름차순으로 정렬하기 위해 출현 빈도 freq에 -를 붙여서 배열에 담았다.

스페이스바를 누르는 횟수까지 포함시켜야 하므로 cnt를 M - 1 로 초기화 하였다.

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

const int ALPHABETS = 26;

int toNumber(char ch) 
{ 
	return ch - 'A'; 
}

struct TrieNode
{
	TrieNode* children[ALPHABETS];
	int first;
	int terminal;

	TrieNode() : terminal(-1), first(-1)
	{
		memset(children, 0, sizeof(children));
	}
	~TrieNode()
	{
		for (int i = 0; i < ALPHABETS; i++)
			if (children[i]) delete children[i];
	}

	void insert(string& key, int here, int id)
	{
		if (first == -1) 
			first = id;

		if (here == key.size())
			terminal = id;
		else
		{
			int next = toNumber(key[here]);

			//자식 노드가 없다면 생성
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1, id);
		}
	}

	int type(string& key, int here, int id)
	{
		if (here == key.size()) return 0;

		if (first == id) return 1;

		int next = toNumber(key[here]);

		return 1 + children[next]->type(key, here + 1, id);
	}

	TrieNode* find(string& key, int here)
	{
		if (here == key.size()) return this;
		
		int next = toNumber(key[here]);

		if (children[next] == NULL) return NULL;
		return children[next]->find(key, here + 1);
	}
};

int countKeys(TrieNode& trie, string word)
{
	TrieNode* node = trie.find(word, 0);

	if (node == NULL || node->terminal == -1)
		return word.size();

	return trie.type(word, 0, node->terminal);
}

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

	int tc;
	cin >> tc;

	while (tc--)
	{
		int N, M;
		cin >> N >> M;

		
		vector<pair<int, string>> input;

		for (int i = 0; i < N; i++)
		{
			string words;
			int freq;
			cin >> words >> freq;
			input.push_back({ -freq, words });
		}

		sort(input.begin(), input.end());

		TrieNode word;
		
		for(int i=0; i<input.size(); i++)
			word.insert(input[i].second, 0, i);
		
		word.first = -1;

		int cnt = M - 1;

		for (int i = 0; i < M; i++)
		{
			string words;
			cin >> words;

			cnt += countKeys(word, words);
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 144 day