코딩하는 두꺼비

www.acmicpc.net/problem/1197

문제를 보고 크루스칼 알고리즘이나 프림알고리즘으로 풀어야 겠다는 생각을 했는데

둘 다 실제로 구현해본적이 없어서 고민을 하다가

결국 답을 보고 풀 수 있었다..

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

int v, e, c;
long long sum;
int visit[10001];
vector<vector<pair<int, int>>> edge;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void prim(int v) {
	visit[v] = 1;		//방문 노드 체크
	for (auto u : edge[v]) {
		if (!visit[u.second]) {		//방문 노드에 연결된 모든 간선 추가
			pq.push({ u.first, u.second });
		}
	}

	while (!pq.empty()) {		//방문 노드와 연결된 간선 중 최소값 더하기
		auto w = pq.top();
		pq.pop();
		if (!visit[w.second]) {
			sum += w.first;
			prim(w.second);
			return;
		}
	}
}

int main() {
	int x, y, z;
	cin >> v >> e;
	edge.resize(v + 1);
	for (int i = 0; i < e; i++) {
		cin >> x >> y >> z;
		edge[x].push_back({ z,y });
		edge[y].push_back({ z,x });
	}
	prim(1);
	cout << sum;
	return 0;
}

출처: dhpark-ghost.herokuapp.com/2018/06/12/c-peurim-prim-algorijeum/

www.acmicpc.net/problem/5014

처음엔 dfs로 해결하려고 문제를 접근했지만 원하는 층에 접근하지 못하는 경우가 있기에 이 부분을 조절할 수 없을 것

같아서 포기했다.

알고리즘 분류를 보지않고 풀려고 했는데 결국 실패하고 분류를 본 후에 bfs임을 알고 문제를 풀 수 있었다ㅠㅠ

문제 분류를 안 후에는 그냥 전형적인 bfs문제라서 편하게 반복문안에 엘베가 위로 올라가는 경우와 내려가는 경우를 모두 고려해서 풀 수 있었다.

쉬운 문제였지만 문제를 보고 알고리즘을 파악하는 방법을 더 키워야 할 것 같다!

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

queue<int> q;
int ans, cnt;
int F, S, G, U, D;

void bfs(int S, vector<int> &v) {
	v[S] = 1;
	q.push(S);
	while (!q.empty()) {
		int s = q.size();
		for (int i = 0; i < s; i++) {
			int x = q.front();
			q.pop();
			if (x == G) {
				ans = cnt;
				return;
			}
			if (x + U <= F && v[x + U] == 0) {
				v[x + U] = 1;
				q.push(x + U);
			}
			if (x - D >= 1 && v[x - D] == 0) {
				v[x - D] = 1;
				q.push(x - D);
			}
		}
		cnt++;
	}
	return;
}

int main() {
	cin >> F >> S >> G >> U >> D;
	vector<int> visit(F+1);
	bfs(S, visit);
	if (S == G) {
		cout << 0;
	}
	else {
		if (ans == 0) {
			cout << "use the stairs";
		}
		else {
			cout << ans;
		}
	}
	return 0;
}