언제나 처음처럼

[문제 링크]

입력받는 버스 노선은 시작정점, 도착정점, 비용으로 이루어져 있다. 시작정점과 도착정점이 명시되어 있기 때문에 필자는 그래프를 무향그래프가 아닌 방향그래프로 만들었다.

또한 같은 노선이 여러개 존재할 수 있다고 명시되어 있기 때문에 이미 연결된 노선과 같은 노선이 입력으로 들어오면 기존 노선의 비용과 비교하여 더 적은 비용을 노선으로 선택하도록 구현하였다.

그래프를 만든 다음 플로이드-와샬 알고리즘을 수행하고 결과를 출력해주면 정답을 받을 수 있다.

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

const int INF = 987654321;
int n, m;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	for (int i = 1; i <= n; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

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

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (adj[a][b] == INF)
			adj[a][b] = c;
		else
			adj[a][b] = min(adj[a][b], c);
	}

	floyd();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (adj[i][j] == INF)
				cout << 0 << ' ';
			else
				cout << adj[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

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

[문제 링크]

입력으로 주어지는 문자열 H와 H의 모든 부분문자열 N에 대해 KMP-search 를 수행하여 H에 N과 일치하는 문자열이 2개 이상 존재하는 N 중에서 길이가 가장 긴 부분문자열의 길이를 출력해주면 된다.

다만, 부분문자열 N의 길이를 1에서부터 시작하면 시간이 너무 오래걸리므로, 이분탐색을 활용하여 시간복잡도를 줄였다. (그래도 오래 걸리는건 함정;;)

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

vector<int> getPartialMatch(string& N) {
	int Nlen = N.length();
	vector<int> pi(Nlen, 0);

	int begin = 1, matched = 0;
	while (begin + matched < Nlen) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}
bool KMP_search(string& H, string& N) {
	int Hlen = H.length(), Nlen = N.length();
	vector<int> pi = getPartialMatch(N);
	int cnt = 0;

	int begin = 0, matched = 0;
	while (begin <= Hlen - Nlen) {
		if (matched < Nlen && H[begin + matched] == N[matched]) {
			matched++;
			if (matched == Nlen) {
				cnt++;
				if (cnt == 2) return true;
			}
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return false;
}

int allPartialStrSearch(string str) {
	int ret = 0;
	int len = str.length();

	int start = 1, end = len;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (mid == 0) break;

		for (int i = 0; i + mid <= len; i++) {
			string N = str.substr(i, mid);
			if (KMP_search(str, N)) {
				ret = mid;
				start = mid + 1;
				break;
			}
		}
		if (start != mid + 1)
			end = mid - 1;
	}

	return ret;
}

int main(void) {
	string str;
	cin >> str;

	cout << allPartialStrSearch(str) << endl;

	return 0;
}

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

[문제 링크]

단순히 위, 왼쪽, 오른쪽, 아래 순으로 탐색하다가 먹을 수 있는 물고기가 발견되면 그 물고기가 문제 조건에 맞는 물고기라 생각하고 풀었다가 고생한 문제였다.

그래서 현재 상태에서 먹을 수 있는 물고기들의 위치를 모두 우선순위큐에 담은 다음 가장 우선순위가 높은 물고기를 먹는 방식으로 구현하여 정답을 받을 수 있었다.

bfs를 계속 반복하면서 물고기를 먹다가 만약 bfs를 했는데 우선순위큐가 비어있다면 맵에 먹을 수 있는 물고기가 없는 것이므로 반복을 종료하고 그동안 움직인 횟수를 출력하면 원하는 결과를 얻을 수 있다.

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

struct Shark {
	int y;
	int x;
	int level;
	int exp;
	int move;

	// 물고기를 먹는다.
	// 경험치가 레벨과 같아지면 레벨업
	void eatFish() {
		exp++;
		if (level == exp) {
			level++;
			exp = 0;
		}
	}
};

// priority_queue 크기 비교를 위한 연산자 오버로딩
bool operator< (const Shark& lhs, const Shark& rhs) {
	if (lhs.move > rhs.move)
		return true;
	else if (lhs.move == rhs.move && lhs.y > rhs.y)
		return true;
	else if (lhs.move == rhs.move && lhs.y == rhs.y && lhs.x > rhs.x)
		return true;

	return false;
}

Shark shark;
int N;
int board[20][20];
// 문제 조건에 따라 북 서 동 남 순으로 탐색
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };

bool bfs() {
	vector<vector<bool>> visited(20, vector<bool>(20, false));
	visited[shark.y][shark.x] = true;

	queue<Shark> q;
	q.push(shark);

	// 먹이로 가능한 좌표를 우선순위가 큰 순서대로 저장
	priority_queue<Shark> pq;

	while (!q.empty()) {
		Shark here = q.front();
		int fish = board[here.y][here.x];
		q.pop();

		if (fish != 0 && fish < here.level) {
			pq.push(here);
			continue;
		}

		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] <= here.level) {
					visited[ny][nx] = true;
					q.push({ ny, nx, here.level, here.exp, here.move + 1 });
				}
		}
	}

	if (!pq.empty()) {
		Shark pick = pq.top();
		board[pick.y][pick.x] = 0;
		shark = pick;
		shark.eatFish();
		return true;
	}

	return false;
}

int main(void) {
	cin >> N;

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

			if (board[i][j] == 9) {
				board[i][j] = 0;
				shark = { i, j, 2, 0, 0 };
			}
		}
	while (1) if (!bfs()) break;
	
	cout << shark.move << endl;

	return 0;
}

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

[문제 링크]

정점들을 연결하는 간선의 가중치가 1인 그래프를 만든 다음, 모든 정점 간의 최단거리를 구하는 플로이드-와샬 알고리즘을 수행하고 모든 정점들의 케빈 베이컨 수를 계산하여 그 값이 가장 작은 인덱스를 출력하도록 구현하였다.

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

const int INF = 987654321;
int N, M;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	for (int i = 1; i <= N; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

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

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;

		adj[A][B] = 1;
		adj[B][A] = 1;
	}

	floyd();

	int temp = INF;
	int idx;
	for (int i = 1; i <= N; i++) {
		int kebin = 0;
		for (int j = 1; j <= N; j++)
			kebin += adj[i][j];

		if (temp > kebin) {
			temp = kebin;
			idx = i;
		}
	}

	cout << idx << endl;

	return 0;
}

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

[문제 링크]

BFS를 통해 같은 집합에 속한 정점들을 방문하면서 같은 레벨에 속한 정점들을 같은 숫자로 마킹한다.

이 과정에서 같은 레벨에 속했는데 이미 다른 숫자로 마킹이 되어있는 정점이 있는 경우 그 그래프는 이분그래프가 아니게 되므로 false를 반환한다.

모든 정점을 방문할 때 까지 위 과정을 반복하면서 false를 반환하지 않았다면 이분그래프이므로 true를 반환하도록 구현하면 원하는 결과를 얻을 수 있다.

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

int V, E;
vector<int> adj[20001];
vector<int> visited;

bool bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 1 });
	visited[start] = 1;

	while (!q.empty()) {
		int here  = q.front().first;
		int color = q.front().second;
		q.pop();

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i];
			
			if (visited[there] == 0) {
				visited[there] = -color;
				q.push({ there, -color });
			}
			else
				if (visited[there] != -color)
					return false;
		}
	}

	return true;
}

bool bfsAll() {
	visited = vector<int>(V + 1, 0);

	for (int i = 1; i <= V; i++)
		if (visited[i] == 0)
			if (!bfs(i)) return false;

	return true;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		cin >> V >> E;
		for (int i = 1; i <= V; i++)
			adj[i].clear();

		for (int i = 0; i < E; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		if (bfsAll())
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

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

[문제 링크]

다익스트라 알고리즘을 이용하는 문제였다.

입력으로 주어지는 버스의 정보를 간선으로 연결하고, 출발 도시를 시작 정점으로 하는 다익스트라 알고리즘을 수행하면 출발 도시에서 모든 도시로 가는 최소 비용을 구할 수 있다. 여기서 도착 도시로 가는 최소 비용을 찾아 출력해주면 원하는 결과를 얻을 수 있다.

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

const int INF = 987654321;
int N, M;
vector<pair<int, int>> adj[1001];

int dijkstra(int start, int arrive){
	vector<int> dist(N+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 nextCost = adj[here][i].second + cost;

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

	return dist[arrive];
}

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

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

	int start, arrive;
	cin >> start >> arrive;

	cout << dijkstra(start, arrive) << endl;

	return 0;
}

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

[문제 링크]

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

#include <iostream>
#include <vector>
#include <queue>
#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 = 1001;
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 + 1; 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;

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