이것 저것 &

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

bfs문제

6087번 레이저 통신과 흡사 

접근방식

1. bfs를 통해서 접근하는 방법을 고안

2. 방향마다 visited(방문값)을 구해주며 진행하여 결과값을 도출하자

문제풀이 

1. 큐에는 현재 좌표, 거울의 개수 순으로 저장

2. visited에는 4방향별로 최소값을 적으며 bfs를 진행

코드로 이해하는게 더 빠를 것 같음

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct a {
	int y;
	int x;
}dir;

int n;
string arr[50];
vector <dir> door;
int visited[50][50][4];
dir d[4] = { {0,1},{1,0},{0,-1},{-1,0} };

void bfs() {

	queue <pair<pair<int, int>,int>> que; // 좌표 방향
	for (int i = 0; i < 4; i++) {
		que.push(make_pair(make_pair(door[0].y, door[0].x),i));
		visited[door[0].y][door[0].x][i] = 1;
	}

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int dir = que.front().second;
		que.pop();

		int ny = y + d[dir].y;
		int nx = x + d[dir].x;
		if (ny < 0 || ny >= n || nx < 0 || nx >= n || arr[ny][nx] == '*')
			continue;

		if (arr[ny][nx] == '.' || arr[ny][nx] == '#') {
			if (visited[ny][nx][dir] > visited[y][x][dir] ||  visited[ny][nx][dir] == 0) {
				visited[ny][nx][dir] = visited[y][x][dir];
				que.push(make_pair(make_pair(ny, nx), dir));
			}
		}
		else if (arr[ny][nx] == '!') {
			if (visited[ny][nx][dir] > visited[y][x][dir]) { //거울 설치 x 
				visited[ny][nx][dir] = visited[y][x][dir];
				que.push(make_pair(make_pair(ny, nx), dir));
			}
			for (int i = 1; i <= 3; i += 2) {
				if (visited[ny][nx][(dir + i) % 4] > visited[y][x][dir] + 1) { // 거울 설치 1
					visited[ny][nx][(dir + i) % 4] = visited[y][x][dir] + 1;
					que.push(make_pair(make_pair(ny, nx), (dir + i) % 4));
				}
			}
			
		}

	}

}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == '#')
				door.push_back({ i,j });
			for (int k = 0; k < 4; k++)
				visited[i][j][k] = 2000000000;
		}
	}

	bfs();


	int result = 2000000000;
	for (int i = 0; i < 4; i++) {
		if(visited[door[1].y][door[1].x][i] != 0)
			result = min(result, visited[door[1].y][door[1].x][i]);
	}
	cout << result - 1 << endl;

	return 0;
}

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

문제 제목처럼 플로이드 와샬 알고리즘 문제이지만.. 다익스트라로 풀었다... (속도차이도 크게 안나요.. 취존...)

접근방식

1. 전형적인 최단거리를 구하는 문제 

2. 다만 모든 좌표에 한해서 최단거리를 구해야하기 때문에 플로이드 와샬문제지만 

쿨하게 다익스트라로 모든 좌표에 대한 최단 거리를 구하고 출력해주었다. 

문제풀이 

1. 전형적인 다익스트라로 구현

2. 모든 점에서 다익스트라 호출

주의할 점은 연결이 불가한 경우엔 0을 출력하는것

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

int n, m;
vector <pair<int, int>> vec[101];
int dist[101];

void dijkstra(int num) {
	priority_queue <pair<int, int>> que;
	que.push(make_pair(0, num));
	dist[num] = 0;

	while (!que.empty()) {
		int cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			int before_v = dist[vec[cur][i].first];
			int current_v = dist[cur] + vec[cur][i].second;

			if (current_v < before_v) {
				dist[vec[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, vec[cur][i].first));
			}

		}


	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	int from, to, cost;
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> cost;
		vec[from].push_back(make_pair(to, cost));
	}
	
	for (int i = 1; i <= n; i++) { // 매 줄마다 반복할거

		for (int j = 1; j <= n; j++)
			dist[j] = 2000000000;

		dijkstra(i);

		for (int j = 1; j <= n; j++) {
			if (dist[j] == 2000000000)
				printf("0 ");
			else
				printf("%d ", dist[j]);
		}
		printf("\n");
	}

	return 0;
}

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

노드마다 최소비용을 구하는 밸만 포드

접근방식

1. 노드마다 최소비용을 구해야 함으로 다익스트라인가 생각함

2. 음수값이 포함됨으로 밸만포드로 구현하자

문제풀이 

1. 전형적인 밸만포드문제. 얍문님 블로그만큼 설명을 잘할 자신이 없어서 링크 첨부

https://yabmoons.tistory.com/365

2. 조심해야할 부분은 dist배열을 long long 자료형을 사용해야 된다는점

정답 코드

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

int n, m;
vector<pair<pair<int, int>, int>> vec;
long long dist[501];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		vec.push_back(make_pair(make_pair(from, to), cost));
	}



	for (int i = 1; i <= n; i++)
		dist[i] = 2000000000;

	dist[1] = 0;

	for (int i = 1; i <= n - 1; i++) {
		for (int j = 0; j < vec.size(); j++) {
			int from = vec[j].first.first;
			int to = vec[j].first.second;
			int cost = vec[j].second;

			if (dist[from] == 2000000000) continue;
			if (dist[to] > dist[from] + cost) {
				dist[to] = dist[from] + cost;
			}

		}

	}

	for (int j = 0; j < vec.size(); j++) {
		int from = vec[j].first.first;
		int to = vec[j].first.second;
		int cost = vec[j].second;

		if (dist[from] == 2000000000) continue;
		if (dist[to] > dist[from] + cost) {
			cout << -1 << endl;
			return 0;
		}

	}

	for (int i = 2; i <= n; i++) {
		if (dist[i] == 2000000000)
			cout << -1 << endl;
		else
			cout << dist[i] << endl;
	}


	return 0;
}

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

MST문제 

접근방식

1. 모든 노드를 잇는 최소비용을 출력하는 것이기 때문에 MST문제임을 인식

2. 우선순위 큐를 사용한 프림알고리즘을 사용하기로 함

문제풀이 

1. 일반적인 프림알고리즘과 거의 동일한 구조

2. 조심해야할 점은 결과값이 소수형태이기 때문에 그 부분에 유의하면서 자료형을 선택해야한다. 

3. dis에 거리를 다 넣어놓고 탐색하는 구조

코드를 보면 더 이해가 빠를 듯

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

int n, m;
bool visited[1001] = { 0, };
int arr[1001][2] = { 0, };	
double dis[1001][1001] = { 0, };
double result = 0;
vector<pair<int, int>> vec;


void prim() {

	priority_queue <pair<double, int>> que; // 비용이랑 몇번째 좌표인지 표기
	for (int i = 2; i <= n; i++) { // 1과 연결된 값을 저장 
		que.push(make_pair(dis[1][i] * -1, i));
	}
	visited[1] = 1;

	while (!que.empty()) {
		double cost = que.top().first * -1;
		int cur = que.top().second;
		que.pop();

		if (visited[cur] == 0) {
			visited[cur] = 1;
			result += cost;

			for (int i = 1; i <= n; i++) {
				if (i != cur && visited[i] == 0) {
					que.push(make_pair(dis[cur][i] * -1, i));
				}
			}
		}


	}

}

int main() {

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> arr[i][0] >> arr[i][1];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			dis[i][j] = sqrt(pow(abs(arr[i][0] - arr[j][0]), 2) + pow(abs(arr[i][1] - arr[j][1]), 2));
			dis[j][i] = dis[i][j];
		}
	//cout << dis[1][2] << endl;

	int t1, t2;
	for (int i = 0; i < m; i++) {
		cin >> t1 >> t2;
		dis[t1][t2] = 0, dis[t2][t1] = 0;
	}

	prim();
	printf("%.2f\n", result);
}

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

다익스트라 + 구현 문제 

접근방식

1. 최단 거리 탐색에서 다익스트라로 구현하면 되겠다 생각

2. 아래 문제와 비슷한 방식

https://gusdnr69.tistory.com/239?category=799066 

결국 s -> g -> h -> 목표 지점 또는 s -> h -> g -> 목표 지점으로 이동할 때의 최소값이 

s -> 목표지점으로 도달하는 값이 똑같은지 비교하는 문제 

3. 다익스트라를 3번 호출해서 구현하자 

문제풀이 

1. 다익스트라는 일반적인 형태와 똑같이 구현. 다만 매개변수에 배열을 넣어서 해당 배열을 채워 주는 구조로 

2. dist배열을 s에서 시작할 때, g에서 시작할 때, h에서 시작할 때 총 3개를 만들고 다익스트라 함수도 총 3번 호출

3.  min( s-g-h-목표 지점, s-h-g-목표지점)이  s-목표지점과 같은지 확인  

정답 코드

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

int T, n, m, t, s, g, h;
int a, b, d, temp;

vector <int> destin; //목적지 위치, 시작점에서 다이렉트로 도달할 때 거리를 저장할거
int dist_s[2001];
int dist_g[2001];
int dist_h[2001];
vector <pair<int,int>> arr[2001];

void dijkstra(int start, int dist[2001]) {
	priority_queue <pair<int,int>> que;
	que.push(make_pair(0, start));
	dist[start] = 0;

	while (!que.empty()) {
		int cost = que.top().first *  -1;
		int cur = que.top().second;
		que.pop();


		for (int i = 0; i < arr[cur].size(); i++) {
			int before_v = dist[arr[cur][i].first];
			int current_v = cost + arr[cur][i].second;
			if (before_v > current_v) {
				dist[arr[cur][i].first] = current_v;
				que.push(make_pair(current_v*-1, arr[cur][i].first));
			}
		}

	}



}



int main() {
	

	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d", &n, &m, &t);
		scanf("%d %d %d", &s, &g, &h);
		
		
		//초기화 
		destin.clear();
		for (int i = 1; i <= 2000; i++) {
			arr[i].clear();
			dist_s[i] = 2000000000;
			dist_g[i] = 2000000000;
			dist_h[i] = 2000000000;
		}
		
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d", &a, &b, &d);
			arr[a].push_back(make_pair(b, d));
			arr[b].push_back(make_pair(a, d));
		}

		for (int i = 0; i < t; i++) {
			scanf("%d", &temp);
			destin.push_back(temp);
		}

		sort(destin.begin(), destin.end()); // 오름차순으로 미리 정렬해둠	

		dijkstra(s, dist_s);
		dijkstra(g, dist_g);
		dijkstra(h, dist_h);

		

		for (int i = 0; i < destin.size(); i++) {

			if (dist_s[destin[i]] == (dist_s[g] + dist_g[h] + dist_h[destin[i]]))
				cout << destin[i] << ' ';
			else if(dist_s[destin[i]] == (dist_s[h] + dist_h[g] + dist_g[destin[i]]))
				cout << destin[i] << ' ';
		}
		cout << endl;


		/*
		cout << endl;
		for (int i = 1; i <= n; i++) {
				cout << dist2[i] << ' ';
		}
		cout << endl;
		*/

	}

	return 0;
}

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

bfs문제입니다.

접근방식

1. 일반적인 공식이나 규칙을 통해서 풀 수 있는 문제가 아님

132 3

이라는 입력값일때, 결과는 321이 아닌 312

312 -> 321 -> 312 이기 때문에

즉, 특정 규칙을 통해서가 아닌 모든 경우를 판단해서 최대값을 도출하는 방향으로 접근함

2. bfs를 통해서 매번 k번만큼 모든경우를 판단해줌 

visited는 k번마다 초기화를 시켜주어야함.

왜냐하면 앞선 예시에서 312라는 값이 앞에서 사용되어졌는데, 결과값이기도 함 

즉, 매번 방문여부를 초기화하며 진행해주어야함 

문제풀이 

1. 우선 -1인 경우를 생각해봄

• 한자리 수일때: 스왑할 수가 없으니 불가
• 두자리 수이고 일의 자리수가 0일때: 스압하게 되면 0이 앞으로 나옴으로 조건에 부합하지 않음 ex) 10, 20, 50

2. BFS를 통해서 구현함

이때, K번만큼 반복하도록 구획을 나눠주면서 진행해야함. 이유는 접근방식 2번 참고

3. BFS에서 문자열에서 한 문자씩 바꿔보면서 visited집합에 값이 있는지 없는지 판단하며 진행

정답 코드

#include <iostream>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

string arr;
int k;
int maxed = 0;
bool jud() {
	int cnt = 0;
	for (int i = 0; i < arr.size(); i++)
		if (arr[i] > '0')
			cnt++;
	if (cnt > 1)
		return true;
	return false;
}

void bfs() {
	queue <string> que;
	que.push(arr);

	for (int u = 0; u < k; u++) { // k번 반복 
		int sized = que.size();
		set <string> visitied;

		for (int s = 0; s < sized; s++) {
			string temp = que.front();
			que.pop();

			for (int i = 0; i < temp.size() - 1; i++) {
				for (int j = i + 1; j < temp.size(); j++) {
					if (i == 0 && temp[j] == '0') continue;

					swap(temp[i], temp[j]); // #include algo
					if (visitied.find(temp) == visitied.end()) {
						if (u == k - 1) { //마지막 턴
							int val = stoi(temp);
							maxed = max(maxed, val);
						}
						que.push(temp);
						visitied.insert(temp);
					}
					swap(temp[i], temp[j]);
				}
			}


		}



	}


}

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

	cin >> arr >> k;
	if (arr.size() == 1) { // 한자리 수
		cout << -1 << endl;
		return 0;
	}
	else if (arr.size() == 2 && jud() == false) { // 두자리 수이지만 수가 하나라 swap을 못할 때
		cout << -1 << endl;
		return 0;
	}

	bfs();

	cout << maxed << endl;

	return 0;
}

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

dp문제입니다.

접근방식

1. 당연히 일반적인 방법으로 매번 검사하는건 불가능하다. 

O(n x m) => 2000 X  1,000,000 으로 가뿐히 10초를 넘기기 때문에

2. dp방식을 통해서 이미 검사해준 값이라면 또 탐색하지 말고 바로 값을 얻어오자

문제풀이 

1. top-down방식으로 dp[시작점][끝점]마다 가능한지 불가능한지 체크해주면서 넘어가자

2. 양 옆으로 한칸씩 줄이면서 탐색하는 구조 자세한 설명은 코드로

정답 코드

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

int n = 0, m = 0, st = 0, en = 0;
int arr[2000] = { 0, };
int dp[2000][2000];

int solved(int s, int e) {
	if (s >= e) return 1;
	if ((s + 1) == e) {
		if (arr[s] == arr[e])
			return 1;
		else
			return 0;
	}

	int& ret = dp[s][e];
	if (ret != -1) return ret;

	if (arr[s] == arr[e])
		ret = solved(s + 1, e - 1);
	else
		ret = 0;

	return ret;
}

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

	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d", &arr[i]);
	
	for (int i = 0; i < 2000; i++)
		for(int j=0; j < 2000; j++)
			dp[i][j] = -1;

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &st,&en);
		printf("%d\n", solved(st - 1, en - 1));
	}


	return 0;
}

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

bfs문제입니다.

접근방식

1. 결국 몇번 꺾여서 목표에 도달할 수 있는지 묻는 문제

2. bfs를 통해서 구현하기로 결정. 일반적인 형태라는 다르게 큐를 구현해야함

문제풀이 

1. 큐에는 현재 좌표, 거울의 개수, 도달한 방향순으로 저장

2. 만약 거울의 갯수가 같거나 작다면 큐에 넣어주면서 거울 갯수를 탐색

이때, visited함수에 최소 거울의 갯수를 저장

정답 코드

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

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };
char arr[100][100];

vector <pair<int, int>> laser;
int visited[100][100] = { 0, };
int w, h;

int val, temp;

void bfs() {

	queue <pair<pair<int, int>, pair<int, int>>> que; //좌표, 거울 갯수, 방향순으로 넣을거
	que.push(make_pair(make_pair(laser[0].first, laser[0].second), make_pair(0, -1)));

	while (!que.empty()) {
		int y = que.front().first.first;
		int x = que.front().first.second;
		int mirror = que.front().second.first;
		int dir = que.front().second.second;
		que.pop();
		int temp;
		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			if (ny < 0 || ny >= h || nx < 0 || nx >= w || arr[ny][nx] == '*' )
				continue;
			temp = mirror;
			if (dir != i)
				temp++;
			if (visited[ny][nx] >= temp) {
				visited[ny][nx] = temp;
				que.push(make_pair(make_pair(ny, nx), make_pair(temp, i)));
			}



		}

		
	}



}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	
	cin >> w >> h;
	for (int i = 0; i < h; i++) {
		cin >> arr[i];
		for (int j = 0; j < w; j++) {
			if (arr[i][j] == 'C')
				arr[i][j] = '.', laser.push_back(make_pair(i, j));
			visited[i][j] = 1000000000;
			
		}
	}

	bfs();
	/*
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cout << visited[i][j] << ' ';
		}
		cout << endl;
	}
	*/

	cout << visited[laser[1].first][laser[1].second] - 1 << endl;

	return 0;
}