슥지니의 코딩노트

문제 링크: https://www.acmicpc.net/problem/1719

<문제 풀이> 플로이드-워셜 알고리즘

nxt[i][j] : i에서 j로의 최단 경로를 따라 i에서 가장 먼저 방문해야 하는 정점

이와 같은 2차원 배열 nxt를 추가로 정의하여 플로이드 알고리즘을 수행합니다.

i에서 j로 이동하는 경로에서 새로운 최단 거리를 갱신하는 장점 k를 찾게 되면, nxt[i][j] = nxt[i][k]로 nxt 배열을 갱신합니다.

이는 i에서 k로의 최단 경로를 따라 이동한 후, k에서 j로의 최단 경로를 이동하기 때문입니다. 따라서 i에서 j로 이동할 때 가장 먼저 방문해야 하는 정점은 i에서 k로 이동할 때 가장 먼저 방문해야 하는 정점인 nxt[i][k]와 같습니다.

<C++소스코드>

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

const int MAX_N = 200;
int n, m;
int graph[MAX_N + 1][MAX_N + 1];
int nxt[MAX_N + 1][MAX_N + 1];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> n >> m;
	memset(graph, 0x3f, sizeof(graph));
	for (int i = 1; i <= n; i++) {
		graph[i][i] = 0;
	}
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		graph[u][v] = w;
		graph[v][u] = w;
		nxt[u][v] = v;
		nxt[v][u] = u;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (graph[i][j] > graph[i][k] + graph[k][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
					nxt[i][j] = nxt[i][k];
				}
			}
		}
	}

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

	return 0;
}

문제 링크: https://www.acmicpc.net/problem/5052

<문제 풀이> 트라이(trie)

트라이를 사용하여 전화번호를 삽입합니다. 삽입할 때마다, 트라이 내에 전화번호의 접두사가 이미 존재하는지 확인해야 합니다.

이를 구현하기 위해서는 find 함수에서 각 노드의 자식 노드의 존재 여부와 전화번호의 끝을 체크해야 합니다.

<C++소스코드>

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

class Trie {
public:
	static const int MX = 10000 * 10;
	static const int ROOT = 1;
	int unused = 2;
	int nxt[MX + 1][10];
	bool check[MX + 1];

	Trie() {
		memset(nxt, 0xff, sizeof(nxt));
		memset(check, 0x00, sizeof(check));
	}
	void insert(const string &s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - '0'] == -1) nxt[cur][c - '0'] = unused++;
			cur = nxt[cur][c - '0'];
		}
		check[cur] = true;
	}
	bool find(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			cur = nxt[cur][c - '0'];
			if (cur == -1) return false;
			else if (check[cur]) return true;
		}
		return true;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int test_case; cin >> test_case;
	while (test_case--) {
		int n; cin >> n;
		string ans = "YES";
		Trie *trie = new Trie();
		for (int i = 0; i < n; i ++) {
			string num; cin >> num;
			if (trie->find(num)) ans = "NO";
			trie->insert(num);
		}
		cout << ans << '\n';
	}

	return 0;
}

문제 링크: https://www.acmicpc.net/problem/14426

<문제 풀이> 트라이(Trie)

트라이를 사용해서 문자열 삽입, 검색

<C++소스코드>

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

class Trie {
public:
	static const int MX = 10000 * 500;
	static const int ROOT = 1;
	int unused = 2;
	int nxt[MX + 1][26];
	Trie() {
		memset(nxt, 0xff, sizeof(nxt));
	}

	void insert(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - 'a'] == -1) nxt[cur][c - 'a'] = unused++;
			cur = nxt[cur][c - 'a'];
		}
	}
	bool find(const string& s) {
		int cur = ROOT;
		for (auto& c : s) {
			if (nxt[cur][c - 'a'] == -1) return false;
			cur = nxt[cur][c - 'a'];
		}
		return true;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	Trie* trie = new Trie();
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		trie->insert(s);
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		string s; cin >> s;
		ans += trie->find(s);
	}
	cout << ans;
	return 0;
}

문제 링크: https://www.acmicpc.net/problem/10217

<문제 풀이> 다익스트라, DP 알고리즘

j의 비용을 사용해서 i번 정점까지의 최단 거리를 저장할 2차원 DP[i][j] 배열을 만들고 다익스트라 알고리즘을 사용하면 됩니다.

최단 거리를 구할 때 2가지 최적화 방법을 적용할 수 있습니다.

1.

정점 u를 비용 c로 방문하여 최단 거리를 갱신할 때, 비용 c보다 큰 비용으로 정점 u를 방문하는 경우는 고려하지 않아도 됩니다. 그 이유는 정점 u에 비용 c로 도달한 상황에서 이미 최단 거리를 갱신했다면, c보다 큰 비용으로 해당 정점을 방문하는 것은 최적의 경로가 될 수 없기 때문입니다. 이를 통해 우선순위큐에 불필요한 삽입을 줄일 수 있습니다.

2. 

각 정점에 연결된 간선들을 비용 기준으로 오름차순 정렬합니다. 다익스트라 알고리즘을 사용하여 다음 정점을 탐색할 때, 해당 정점까지의 비용 cost가 최대 지원 비용 M을 초과하는 경우, 그 이후의 간선들은 검사할 필요가 없습니다.

<C++소스코드>

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

const int MAX_N = 100;
const int MAX_M = 10000;
const int INF = 0x3f3f3f3f;
int N, M, K;
int dist[MAX_N + 1][MAX_M + 1];
vector<tuple<int, int, int> > adj[MAX_N + 1];

bool CmpCost(tuple<int, int, int>& a, tuple<int, int, int>& b) {
    return get<1>(a) < get<1>(b);
}

void init() {
    for (int i = 0; i <= N; i++) {
        adj[i] = {};
    }
    memset(dist, 0x3f, sizeof(dist));
}

int dijkstra(int st) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > pq;
    dist[st][0] = 0;
    pq.push({ dist[st][0], 0, st });
    while (!pq.empty()) {
        int cur_dist, cur_cost, cur_idx;
        tie(cur_dist, cur_cost, cur_idx) = pq.top(); pq.pop();

        if (dist[cur_idx][cur_cost] != cur_dist) continue;

        for (auto& nxt : adj[cur_idx]) {
            int d, c, v; tie(d, c, v) = nxt;
            int nxt_dist = cur_dist + d;
            int nxt_cost = cur_cost + c;
            int nxt_idx = v;

            if (nxt_cost > M) break;

            if (nxt_dist < dist[nxt_idx][nxt_cost]) {
                for (int i = nxt_cost; i <= M; i++) {
                    if (dist[nxt_idx][i] <= nxt_dist) break;
                    dist[nxt_idx][i] = nxt_dist;
                }
                pq.push({ dist[nxt_idx][nxt_cost], nxt_cost, nxt_idx });
            }
        }
    }
    int ret = INF;
    for (int i = 0; i <= M; i++) {
        ret = min(ret, dist[N][i]);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int test_case; cin >> test_case;
    while (test_case--) {
        init();
        cin >> N >> M >> K;
        for (int i = 0; i < K; i++) {
            int u, v, c, d; cin >> u >> v >> c >> d;
            adj[u].push_back({ d, c, v });
        }
        for (int i = 1; i <= N; i++) {
            sort(adj[i].begin(), adj[i].end(), CmpCost);
        }
        int ans = dijkstra(1);
        if (ans >= INF) cout << "Poor KCM\n";
        else cout << ans << '\n';
    }

    return 0;
}

문제 링크: https://www.acmicpc.net/problem/1948

<문제 풀이> 그래프 탐색, 위상 정렬

도착 도시에 가장 마지막에 도착하는 시간은 해당 도시로 들어오는 모든 출발 도시들이 도착한 시점입니다. 이를 모든 도시에 대해 순차적으로 고려하면 DAG이기 때문에 위상 정렬로 답을 구할 수 있습니다.

도로를 지나는 횟수를 계산하기 위해 역방향 간선을 추가로 입력 받아 도착 도시에서 BFS를 수행합니다. 만약 u에서 v로 이동하는데 필요한 시간이 cost라고 한다면, (u에 마지막으로 도착하는 시간 - cost == v에 마지막으로 도착하는 시간)이라면, 해당 간선은 위상 정렬에서 사용되었기 때문에 카운트해 주면 됩니다.

<C++소스코드>

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

const int MAX_N = 10000;

int n, m;
vector<pair<int, int> >adj[MAX_N + 1];
vector<pair<int, int> >rev_adj[MAX_N + 1];
bool visited[MAX_N + 1];
int indegree[MAX_N + 1];
int dist[MAX_N + 1];
int st, en;

int TopologicalSort() {
    queue<int> Q;
    Q.push(st);
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& nxt : adj[cur]) {
            int nxt_dist = nxt.first + dist[cur];
            int nxt_idx = nxt.second;
            if (dist[nxt_idx] < nxt_dist) {
                dist[nxt_idx] = nxt_dist;
            }
            indegree[nxt_idx]--;
            if (indegree[nxt_idx] == 0) {
                Q.push(nxt_idx);
            }
        }
    }
    return dist[en];
}

int FindPath() {
    queue<int> Q;
    Q.push(en);
    int ret = 0;
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        for (auto& nxt : rev_adj[cur]) {
            int cost = nxt.first;
            int nxt_idx = nxt.second;
            if (dist[cur] - cost == dist[nxt_idx]) {
                ret++;
                if (!visited[nxt_idx]) {
                    visited[nxt_idx] = true;
                    Q.push(nxt_idx);
                }
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({ w, v });
        indegree[v]++;
        rev_adj[v].push_back({ w, u });
    }

    cin >> st >> en;
    cout << TopologicalSort() << '\n';
    cout << FindPath();
    return 0;
}

문제 링크: https://www.acmicpc.net/problem/24042

<문제 풀이> 다익스트라 알고리즘

횡단보도를 건너기 위해 파란불이 켜지기를 기다려야 합니다. 이 대기 시간을 '가중치'라고 생각할 수 있습니다. 또한 횡단보도의 파란불은 주기를 가지고 있기 때문에, 이 문제에서는 각 간선이 여러 개의 가중치를 가질 수 있습니다.

A - B 간의 가중치는 i, M + i, 2M + i, 3M + i,... 와 같은 값을 가질 수 있습니다. 문제를 해결하기 위해, 다익스트라 알고리즘을 사용하여 다음 정점을 방문할 때 현재 가능한 가장 작은 가중치를 선택해 나가면 됩니다. 다익스트라 알고리즘을 사용하면서 모든 가능한 가중치를 미리  계산하여 삽입할 필요는 없습니다. 대신 문제에서 주어진 초기 가중치 i로부터 동적으로 값을 계산해나가야 합니다.

여기서 중요한 것은, A까지 도달했을 때의 시간보다 크면서 가장 작은 가중치를 선택해야 됩니다. 이를 위해 주기 M을 계속 더해서 가중치를 구하면 시간 초과가 발생합니다.

초기 가중치가 i일 때, 현재 시간을 t라고 가정하면, 초기 가중치 i에 M을 반복적으로 더하는 대신  M을 몇 번 더해야 할지를 계산하고 그 횟수를 M에 곱해서 초기 가중치 i에 더하면 O(1)에 가중치를 구할 수 있습니다.

이를 위해 현재 시간 t에서 초기 가중치 i를 빼고, 그 결과를 M으로 나누면, i에서 M을 몇 번 더해야 원하는 가중치를 얻을 수 있는지 바로 알 수 있습니다.

<C++소스코드>

#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<cstring>
#include<functional>
#include<cmath>
using namespace std;


typedef long long ll;

const int MAX_N = 100000;
vector<pair<ll, int> > adj[MAX_N + 1];
ll d[MAX_N + 1];
int N, M;

ll dijkstra(int st) {
    memset(d, 0x3f, sizeof(d));
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    d[st] = 0;
    pq.push({ d[st], st });
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        ll cur_dist = cur.first;
        int cur_idx = cur.second;
        if (d[cur_idx] != cur_dist) continue;

        for (auto& nxt : adj[cur_idx]) {
            ll nxt_dist = nxt.first;
            int nxt_idx = nxt.second;
            if (cur_dist > nxt_dist) {
                nxt_dist += (ceil(((double)(cur_dist - nxt_dist)) / M)) * M;
            }
            if (d[nxt_idx] > nxt_dist) {
                d[nxt_idx] = nxt_dist;
                pq.push({ d[nxt_idx], nxt_idx });
            }
        }
    }
    return d[N];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (ll i = 1; i <= M; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({ i, v });
        adj[v].push_back({ i, u });
    }

    cout << dijkstra(1);


    return 0;
}

문제 링크: https://www.acmicpc.net/problem/14938

<문제 풀이> 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘을 사용하여 각 정점에서 다른 모든 정점까지의 최단거리를 구하고, 탐색 범위 내에 존재하는 아이템들을 선택하면 됩니다.

<C++소스코드>

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

const int MAX_N = 100;

int items[MAX_N + 1];
int d[MAX_N + 1][MAX_N + 1];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int n, m, r; cin >> n >> m >> r;
    for (int i = 1; i <= n; i++) {
        cin >> items[i];
    }
    memset(d, 0x3f, sizeof(d));

    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for (int i = 0; i < r; i++) {
        int u, v, w; cin >> u >> v >> w;
        d[u][v] = w;
        d[v][u] = w;
    }

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

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int temp = 0;
        for (int j = 1; j <= n; j++) {
            if (d[i][j] <= m) {
                temp += items[j];
            }
        }
        ans = max(ans, temp);
    }
    cout << ans;

    return 0;
}

문제 링크: https://www.acmicpc.net/problem/6497

<문제 풀이> 최소 스패닝 트리, 크루스칼 알고리즘

크루스칼 알고리즘으로 최소 비용으로 모든 집을 연결하고, 연결된 비용의 총합을 전체 간선의 비용 총합에서 빼주면 됩니다.

<C++소스코드>

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

const int MAX_N = 200000;
vector<tuple<int, int, int> > edge;
int parents[MAX_N];

int Find(int x) {
    if (parents[x] == x) return x;
    return parents[x] = Find(parents[x]);
}

void Union(int x, int y) {
    int x_parents = Find(x);
    int y_parents = Find(y);
    if (x_parents < y_parents) parents[x_parents] = y_parents;
    else parents[y_parents] = x_parents;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
  
    while (true) {
        int n, m; cin >> n >> m;
        if (n == 0 && m == 0) break;
        edge = {};
        for (int i = 0; i < n; i++) parents[i] = i;

        int tot = 0;
        for (int i = 0; i < m; i++) {
            int u, v, w; cin >> u >> v >> w;
            edge.push_back({ w, u, v });
            tot += w;
        }

        sort(edge.begin(), edge.end());
        int cnt = 0, res = 0;
        for (auto& e : edge) {
            int w, u, v; tie(w, u, v) = e;
            if (Find(u) == Find(v)) continue;
            Union(u, v);
            cnt++;
            res += w;
            if (cnt == n - 1) break;
        }
        cout << tot - res<<'\n';
    }

    return 0;
}