구현 팁

1. 배열에서의 시계방향, 반시계방향

bool map[SIZE]; // 원 형태의 map을 배열로 구현
int move; // 움직일 거리
int idx = 0; // map에서의 현재 위치

idx += move;

if(idx >= 0) idx %= SIZE; // 시계, 반시계 방향으로 움직였을 때 
else idx += SIZE; // 반시계 방향으로 움직였을 때

 

2. 최단경로

1) 다익스트라 : 하나의 정점에서 다른 모든 정점으로의 최단 거리

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

struct comp{
	bool operator()(pair<int, int> a, pair<int, int> b){
		return a.second > b.second;
	}
};

int N, M, s, d, c;
vector<vector<pair<int, int>>> e;
int dp[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M; // 정점, 간선 개수
	e.resize(N + 1);
	for (int i = 1; i <= N; i++)
		dp[i] = 987654321;
	
	for (int i = 0; i < M; i++){
		cin >> s >> d >> c;
		e[s].push_back({ d, c });
	}
	cin >> s >> d; // src, dest

	dp[s] = 0; // 시작점
	pq.push({ s, 0 });

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

		if (dp[src] < cost) // 이전 탐색으로 최단 거리로 갱신되었을 경우
			continue;

		for (int i = 0; i < e[src].size(); i++){
			int dest = e[src][i].first,
            	ccost = dp[src] + e[src][i].second; // 현재(src)까지 비용 + 다음 정점(dest)까지 비용

			if (dp[dest] > ccost){ // 기존의 dest 비용이 더 크다면 갱신
				pq.push({ dest, ccost });
				dp[dest] = ccost;
			}
		}
	}

	cout << dp[d];

	return 0;
}

 

 

3. 유니온파인드

int find(int n){
	if (parent[n] == n)
		return n;
	
	return parent[n] = find(parent[n]);
}

void merge(int n1, int n2){
	int x = find(n1);
	int y = find(n2);

	if (x != y)
		parent[max(x, y)] = min(x, y);
}