언제나 처음처럼

[문제 링크]

 문제를 해결하기 위해 4가지 과정을 반복하였다.

1) iceMelt() 함수를 통해 빙산 주변에 있는 물의 수만큼 빙산을 녹인다.

2) 빙산이 2개 이상으로 나뉘어져 있는지 확인하기 위해 isSeparate() 함수를 정의하고, dfs() 를 통해 한 덩어리에 속한 빙산을 방문한다.

3)  만약 dfs()를 수행할 빙산이 없다면 모두 녹았다는 의미로 2를 반환한다.

4) dfs()를 수행했는데 아직 방문하지 않은 빙산이 있다면 분리되었다는 의미인 1을 반환하고, 모두 방문했다면 2개 이상으로 분리되지 않았다는 의미인 0을 반환한다.

isSeparate() 이 0을 반환했다면 위 과정을 다시 수행하고, 1을 반환했다면 누적한 시간을 출력, 2를 반환했다면 0을 출력한다.

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

struct Pos {
	int y;
	int x;
};

int N, M;
int board[300][300];
bool visited[300][300];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void dfs(Pos here) {
	visited[here.y][here.x] = true;

	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 < M)
			if (!visited[ny][nx] && board[ny][nx] != 0)
				dfs({ ny, nx });
	}
}

int isSeparate() {
	memset(visited, false, sizeof(visited));

	bool check = false;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] != 0 && !visited[i][j]) {
				if (!check) {
					dfs({ i, j });
					check = true;
				}
				else 
					return 1;
			}

	if (!check) 
		return 2;
	else 
		return 0;
}

void iceMelt() {
	int temp[300][300];
	memcpy(temp, board, sizeof(board));

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++) {
			if (temp[i][j] != 0) {
				int water = 0;
				for (int k = 0; k < 4; k++) {
					int ny = i + dy[k];
					int nx = j + dx[k];
					if (ny >= 0 && ny < N && nx >= 0 && nx < M)
						if (temp[ny][nx] == 0) water++;
				}
				board[i][j] -= water;
				if (board[i][j] < 0) board[i][j] = 0;
			}
		}
}

int solution() {
	int years = 0;
	int separate = isSeparate();

	while (separate == 0) {
		years++;
		iceMelt();
		separate = isSeparate();
	}

	if (separate == 1)
		return years;
	else
		return 0;
}

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

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

	cout << solution() << endl;

	return 0;
}

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

[문제 링크]

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

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

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

#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