취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 10977번 문제인 음식 조합 세기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10977

이 문제에서는 레스토랑의 메뉴들이 매일매일 다음 숫자의 메뉴로 바뀔 때 이 메뉴들의 주기를 구하는 문제이다.

즉, 이 문제는 다음과 같은 문제로 바꿔 생각할 수 있다:

첫 index가 1인, 0과 1로 이루어진 문자열에서 가장 짧은 반복주기를 계산한다. (단, 0은 해당 메뉴가 오늘 나오지 않았을 때, 1은 해당 메뉴가 오늘 나왔을 때에 대응된다)

이는 KMP 알고리즘을 구성할 때 사용하는 pi 배열을 이용하여 쉽게 계산할 수 있다.

아래는 제출한 소스코드이다.

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

int food[1000000];
int pi[1000000];

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

    int T; cin >> T;
    while (T--) {
        memset(food, 0, sizeof(food));
        memset(pi, 0, sizeof(pi));
        int M, N; cin >> M >> N;

        while (N--) {
            int x; cin >> x;
            food[x - 1] = 1;
        }

        for (int i = 0; i < M; i++) {
            int idx = i;
            while (idx > 0) {
                if (food[pi[idx - 1]] == food[i]) break;
                idx = pi[idx - 1];
            }
            if (idx <= 0) pi[i] = 0;
            else pi[i] = pi[idx - 1] + 1;
        }
        int temp = M - pi[M - 1];
        if (M % temp == 0) cout << temp << '\n';
        else cout << M << '\n';
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1219번 문제인 오민식의 고민이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1219

이 문제에서는 기본적으로는 어떤 그래프 위 출발 노드에서 도착 노드로 가는 경로 중, 가중치(버는 돈)가 가장 큰 경로를 탐색하는 문제이다. 경로에 따라 돈을 벌 수도 있고 잃을 수도 있으므로, 음수 가중치를 다룰 수 있는 알고리즘인 Bellman-Ford(벨만-포드) 알고리즘이 이 문제를 해결하는 데에 적합하다. 다만, 세부적으로 나누어 출력할 대상이 많으므로 신중하게 코드를 작성해야 한다.

다음은 이 문제를 틀리지 않기 위해 주의해야하는 점들이다.

1. 가중치가 양수인 사이클(돈을 무수히 벌 수 있는 사이클)이 존재한다고 항상 답이 "Gee"가 되지는 않는다. 이 사이클을 계속 빙빙 돌면 돈을 무수히 벌 수 있는 것은 사실이지만, 돈을 벌더라도 경로의 종점이 되어야 하는 "도착 도시"로 갈 수 없다면 이러한 사이클의 존재는 의미가 없어진다.

2. 문제에서 주어진 100개의 도시가 하나의 큰 사이클을 이루고, 각 도시를 방문할 때마다 1,000,000만큼의 돈을 번다면, 각 에지를 아직 한번씩만 살펴보았는데도 100,000,000만큼의 가중치가 쌓이게 된다. 이 사이클을 100번 돌게 되면 10,000,000,000의 가중치가 쌓이게 되는데, 이는 32bit 정수의 표현범위를 넘어가는 수이다. 따라서, 이 문제를 해결하기 해서는 가중치를 저장하는 배열을 64bit 정수로 선언해야한다.

글쓴이는 이 문제의 출력조건을 아래와 같이 구분하였다.

1) 도착 도시에 도달할 수 없는 경우 "gg"를 출력

2) 가중치가 양수인 사이클(돈을 무수히 벌 수 있는 사이클) 위의 점들에서 도착 도시로 갈 수 있는 경로가 있는지 DFS로 확인 후, 존재한다면 "Gee" 출력

3) 그 외의 경우 Bellman-Ford로 계산된 경로의 최대가중치 출력

아래는 제출한 소스코드이다.

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

vector<int> G[100];
vector<int> Gi[100];
long long money[100];
int way[100][3];

vector<int> stk;
bool visited[100];

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

	int N, S, E, M; cin >> N >> S >> E >> M;
	for (int i = 0; i < M; i++) {
		cin >> way[i][0] >> way[i][1] >> way[i][2];
		G[way[i][0]].push_back(way[i][1]);
		Gi[way[i][1]].push_back(i);
	}

	for (int i = 0; i < N; i++) {
		money[i] = -1000000007;
	}

	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		for (auto node : Gi[i]) {
			way[node][2] = x - way[node][2];
		}
		if (i == S) money[i] = x;
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (money[way[j][0]] == -1000000007) continue;
			if (money[way[j][1]] < money[way[j][0]] + way[j][2])
				money[way[j][1]] = money[way[j][0]] + way[j][2];
		}
	}

	// cycle 위에 있는 점들을 stk에 넣고 DFS를 통해 이 점들에서 도착 도시로 갈 수 있는지 확인
	for (int j = 0; j < M; j++) {
		if (money[way[j][0]] == -1000000007) continue;
		if (money[way[j][1]] < money[way[j][0]] + way[j][2]) {
			if (!visited[way[j][0]]) {
				stk.push_back(way[j][0]);
				visited[way[j][0]] = 1;
			}
		}
	}

	// dfs
	while (!stk.empty()) {
		int current = stk.back();
		stk.pop_back();
		for (auto node : G[current]) {
			if (visited[node]) continue;
			visited[node] = 1;
			stk.push_back(node);
		}
	}

	if (money[E] == -1000000007) cout << "gg";
	else if (visited[E]) cout << "Gee";
	else cout << money[E];
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1865번 문제인 웜홀이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11657

이 문제에서는 음수 가중치의 간선이 있는 그래프에서 1번 노드에서 각 다른 노드까지의 경로의 최소 가중치를 구하는 문제이다. 단, 음수 가중치 사이클이 존재하는 경우를 예외처리해주어야 한다.

이 문제가 다루고 있는 내용은 Bellman-Ford(벨만-포드) 알고리즘이 해결하고자 하는 문제와 동일하므로, 자세한 문제풀이 과정은 생략한다.

이 문제를 풀기 위해 Bellman-Ford 알고리즘을 구현할 때 주의해야할 점이 하나 있는데, 간선들을 한번 순회할 때 과거로 10,000 * 6,000 = 60,000,000만큼의 시간을 거슬러 올라갈 수 있다는 점이다. 이를 500번 반복한다면, 거슬러올라가는 시간은 30,000,000,000으로, 부호가 있는 32비트 정수 자료형에서 언더플로우(underflow)가 발생하게 된다. 따라서 이 문제에서는 최단거리를 저장하는 배열은 64비트 정수 자료형을 이용해야한다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

long long dist[501];
long long bus[6000][3];

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

	int N, M; cin >> N >> M;

	for (int i = 2; i <= N; i++) dist[i] = 1000000007;

	for (int i = 0; i < M; i++) {
		cin >> bus[i][0] >> bus[i][1] >> bus[i][2];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (dist[bus[j][0]] == 1000000007) continue;
			if (dist[bus[j][1]] > dist[bus[j][0]] + bus[j][2])
				dist[bus[j][1]] = dist[bus[j][0]] + bus[j][2];
		}
	}

	bool chk = 0;
	for (int j = 0; j < M; j++) {
		if (dist[bus[j][0]] == 1000000007) continue;
		if (dist[bus[j][1]] > dist[bus[j][0]] + bus[j][2])
			chk = 1;
	}

	if (chk) cout << -1;
	else {
		for (int i = 2; i <= N; i++) {
			if (dist[i] == 1000000007) cout << -1 << '\n';
			else cout << dist[i] << '\n';
		}
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1865번 문제인 웜홀이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1865

이 문제는 음수 가중치 간선이 있는 방향그래프에서 음수 가중치인 사이클이 존재하는지 판단하는 문제이다.

"한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우"가 존재한다는 것은 결국 그 지점을 포함하는 음수 가중치인 사이클이 존재한다는 뜻이기 때문이다.

그래프에서 음수 가중치 사이클이 존재하는지를 판단하는 것은 Bellman-Ford(벨만-포드)알고리즘을 응용하여 해결할 수 있다. 음수 가중치 사이클이 없다면 두 노드 사이의 최단경로는 같은 노드를 두번 이상 포함하지 않으므로, 그 경로의 길이는 그래프의 총 노드개수 이하일 수밖에 없다는 점을 이용하는 것이다.

특정 한 점이 아닌 모든 점에 대하여 음수 가중치 사이클이 있는지 한번에 확인해야 효율적이므로, 일반적인 Bellman-Ford의 구현에 포함되어 있는 "이 점이 이미 방문한 점인지를 확인하는 과정"을 생략하는 것이 좋다. (주어진 그래프가 connected(연결그래프)라는 보장이 없기 때문이다.)

이외에도 Floyd-Warshall(플로이드-워셜) 알고리즘을 이용한 음수 가중치 사이클 판단법을 이용해도 이 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int dist[501];
int edges[5201][3];

void solve() {
	int N, M, W; cin >> N >> M >> W;

	int idx = 0;
	while (M--) {
		int S, E, T; cin >> S >> E >> T;
		edges[idx][0] = S, edges[idx][1] = E, edges[idx][2] = T;
		idx++;
		edges[idx][0] = E, edges[idx][1] = S, edges[idx][2] = T;
		idx++;
	}
	while (W--) {
		int S, E, T; cin >> S >> E >> T;
		edges[idx][0] = S, edges[idx][1] = E, edges[idx][2] = -T;
		idx++;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < idx; j++) {
			if (dist[edges[j][1]] > dist[edges[j][0]] + edges[j][2])
				dist[edges[j][1]] = dist[edges[j][0]] + edges[j][2];
		}
	}

	bool ans = 0;

	for (int j = 0; j < idx; j++) {
		if (dist[edges[j][1]] > dist[edges[j][0]] + edges[j][2])
			ans = 1;
	}

	if (ans) cout << "YES\n";
	else cout << "NO\n";
}

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

	int T; cin >> T;
	while (T--) {
		solve();
	}
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11563번 문제인 연돌이와 고잠녀이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11563

이 문제에서는 서로 교점이 없는 두 선분들의 집합 사이의 최단거리를 구해야 한다.

각 집합의 크기가 최대 2000이므로, 가능한 모든 쌍의 선분(최대 400만쌍)에 대하여 거리를 재는 방식으로 이 문제를 풀 수 있다.

두 선분 AB와 CD 사이의 최단거리는 아래와 같은 후보들 중 하나이다.

1) AC, AD, BC, BD의 길이

2) A에서 CD에 내린 수선, B에서 CD에 내린 수선, C에서 AB에 내린 수선, D에서 AB에 내린 수선의 길이

단, 2에서 해당 수선의 발이 선분의 위가 아닌 연장선상에 있다면 그 값은 후보가 될 수 없다.

점 X에서 선분 YZ에 내린 수선의 발이 선분 위에 있는지 확인하는 방법은 내적을 이용하는 것이다. 구체적으로는 벡터 YX와 YZ의 내적, ZX와 ZY의 내적 값이 각각 양수이면 수선의 발이 선분 위에 있게 된다. (증명은 어렵지 않으므로 생략한다)

점 X와 선분 YZ 사이의 거리는 2 * (삼각형 XYZ의 넓이) / (YZ의 길이) 로 구할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<double, double> pd;

double dist(pd pt1, pd pt2){
	return sqrt((pt1.first - pt2.first) * (pt1.first - pt2.first) + (pt1.second - pt2.second) * (pt1.second - pt2.second));
}

double innerproduct(pd pt1, pd pt2, pd pt3) {
	return (pt2.first - pt1.first) * (pt3.first - pt1.first) + (pt2.second - pt1.second) * (pt3.second - pt1.second);
}

double area(pd pt1, pd pt2, pd pt3) { // 수선길이 = 2 * 넓이 / 밑변길이 이므로 넓이를 구할 때 1/2를 하지 않음
	return abs((pt1.first * pt2.second + pt2.first * pt3.second + pt3.first * pt1.second 
		- pt1.first * pt3.second - pt3.first * pt2.second - pt2.first * pt1.second));
}

double segmentdist(pd pt1, pd pt2, pd pt3, pd pt4) {
	double ret = min(min(dist(pt1, pt3), dist(pt1, pt4)), min(dist(pt2, pt3), dist(pt2, pt4)));
	if (innerproduct(pt1, pt3, pt2) > 0 && innerproduct(pt2, pt3, pt1) > 0)
		ret = min(ret, area(pt1, pt2, pt3) / dist(pt1, pt2));
	if (innerproduct(pt1, pt4, pt2) > 0 && innerproduct(pt2, pt4, pt1) > 0)
		ret = min(ret, area(pt1, pt2, pt4) / dist(pt1, pt2));
	if (innerproduct(pt3, pt1, pt4) > 0 && innerproduct(pt4, pt1, pt3) > 0)
		ret = min(ret, area(pt3, pt4, pt1) / dist(pt3, pt4));
	if (innerproduct(pt3, pt2, pt4) > 0 && innerproduct(pt4, pt2, pt3) > 0)
		ret = min(ret, area(pt3, pt4, pt2) / dist(pt3, pt4));
	return ret;
}

pd sinchon[2000][2];

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

	double ans = 100000;

	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		double x, y, z, w; cin >> x >> y >> z >> w;
		sinchon[i][0] = { x,y }, sinchon[i][1] = { z,w };
	}

	for (int j = 0; j < M; j++) {
		double x, y, z, w; cin >> x >> y >> z >> w;
		pd pt3 = { x,y }, pt4 = { z,w };
		for (int i = 0; i < N; i++) {
			ans = min(ans, segmentdist(sinchon[i][0], sinchon[i][1], pt3, pt4));
		}
	}
	cout << fixed;
	cout.precision(10);
	cout << ans;
}

innerproduct(pt1, pt2, pt3): 벡터 pt1pt2와 벡터 pt1pt3의 내적을 계산한다.

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11562번 문제인 백양로 브레이크이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11562

이 문제를 해결하기 위해 먼저 간단한 관찰을 하자.

한 건물에서 다른 건물로 가는 경로는 (일방통행 길을 반대 방향으로 지나가는 경우를 포함하여) 여러 개가 있을 수 있다. 이 문제에서는 이 경로들 중 "일방통행 길을 반대 방향으로 지나가는 횟수"가 최소인 경우의 그 횟수를 구해야한다.

따라서, 일방통행 길을 반대방향으로 지날 때마다 가중치가 1씩 늘어나게 그래프를 만들면 최단경로 알고리즘을 통해 한 점에서 다른 점으로 가는 가장 가중치가 적은 경로와 그때의 가중치(일방통행 길을 반대방향으로 지난 횟수)를 구할 수 있게 된다.

이 문제에서는 여러 쌍의 점에 대하여 질의가 들어오므로, 미리 모든 쌍의 점에 대한 가중치를 계산할 수 있는 Floyd-Warshall(플로이드-워셜) 알고리즘을 이용하는 것이 좋다.

글쓴이 기준으로 이 문제를 dijkstra로 풀어 제출하였을 때에는 864ms, Floyd-Warshall로 풀어 제출하였을 때에는 24ms의 시간이 걸렸다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int dist[251][251];

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

	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = 999;
		}
	}
	for (int i = 1; i <= N; i++) dist[i][i] = 0;

	while (M--) {
		int x, y, z; cin >> x >> y >> z;
		dist[x][y] = 0;
		if (z) dist[y][x] = 0;
		else dist[y][x] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				int temp = dist[i][k] + dist[k][j];
				if (dist[i][j] > temp) dist[i][j] = temp;
			}
		}
	}

	int K; cin >> K;
	while (K--) {
		int s, e; cin >> s >> e;
		cout << dist[s][e] << '\n';
	}
}