이것 저것 &

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

1753번 문제와 똑같습니다. 한 정점에서의 최단경로를 구하기 위해서 다익스트라를 구현해야 합니다.  

다익스트라를 구현할때 우선순위 큐를 사용해야 합니다. 

min-heap을 이용해서 가장 작은 경로값 부터 적용해주며 진행하여야 컴팩트하게 구현할 수 있습니다.(일반 큐를 사용하면 틀립니다.)

정답코드입니다.

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


int a = 0, b = 0; // 출발지, 도착지
int n = 0; // 도시의 개수
int m = 0; // 버스의 개수

vector <int> result;
vector <pair<int, int>> m_arr[1001];

void soultion(int start_index) {

	for (int i = 0; i <= n; i++)
		result.push_back(1000000000); // 최대 값으로 초기화

	priority_queue <pair <int, int >> que; //우선 순위 큐 생성
	que.push(make_pair(0,start_index));

	while (que.empty() == 0) {
		int cost = - que.top().first;
		int destination = que.top().second;
		que.pop();

		if (result[destination] < cost) continue; // 기존 경로가 더 가까우면 continue

		for (int i = 0; i < m_arr[destination].size(); i++) {
			int adjacent_cost =  m_arr[destination][i].second ;
			int adjacent_des = m_arr[destination][i].first;

			if (result[adjacent_des] > adjacent_cost + cost ) {
				result[adjacent_des] = adjacent_cost;
				que.push(make_pair(-result[adjacent_des], adjacent_des));
			}
		}

	}

}

int main(){
	cin >> n;
	cin >> m;
	int u, l, k;
	for (int i = 0; i < m; i++) {
		cin >> u >> l >> k;
		m_arr[u].push_back(make_pair(l, k)); // 
	}
	cin >> a >> b;

	soultion(a);

	cout << result[b] << endl;

	return 0;
}

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

위 문제도 참고하세요. 

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

구현문제입니다. 기존의 방식대로 구현하면 a + b + c = d 를 구하는 문제이기 때문에  O(n^3)이기 때문에 당연히 시간 초과 입니다. O(n^2)만에 해결해야 합니다. 

방법은 a + b = d - c 로 변환 하여 해결하는 것입니다.

i번째마다 이전 두개의 값 조합(a + b)으로 (d - c)를 만들 수 있는지 판별하고,

i까지의 값들의 두개의 값 조합(a + b)을 추가해주며 진행됩니다.

아래는 정답코드입니다. 구현이전 까지의 설계가 어렵고 구현자체는 쉬운 문제였습니다. 

#include <iostream>
using namespace std;

int n = 0, result = 0;
int arr[5000] = { 0 };
bool r[400000] = { 0 };

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



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


	for (int i = 0; i < n; i++) {

		
	
		for (int j = 0; j < i; j++) { // a + b = d - c
			if (r[arr[i] - arr[j] + 200000]) {
				result++;
				//cout << arr[i] << endl;
				break;
			}
		}
		
		for (int j = 0; j <= i; j++) { // a + b check
			r[arr[i] + arr[j] + 200000] = 1;
		}
	}
	cout << result << endl;
}

다익스트라 알고리즘을 이용해서 해결해야 하는 문제입니다.

왜? 그냥 que를 이용해서 구현하면 안되나 생각했습니다. 결과는 

인접하는 정점으로 이동할때는 최소경로값으로 먼저 이동하면서 큐에 들어가는 갯수를 최소화 시켜줘야 합니다.

하나의 정점에서 모든 정점으로 이동하는 최소경로값 (양수만) 이기 때문에 해당 다익스트라 기법을 구현하면 됩니다.  

https://gusdnr69.tistory.com/133

그리고 또 조심하셔야 할게 vector를 사용하지 않고 20000 X 20000 배열을 생성하면 메모리 초과입니다..

이 두 가지를 조심하며 작성해주시면 됩니다.  

구현하는 방법은 bfs와 흡사합니다.

정답코드입니다.

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

int v = 0, e = 0, k = 0;

vector <pair <int, int>> arr[20001];
vector <int> result;

void solution(){

	for (int i = 0; i < v + 1; i++)
		result.push_back(123456789);

	priority_queue <pair <int, int>> que; //우선순위큐
	que.push(make_pair(0, k)); //초기비용0 과 시작점 // min 우선순위큐를 사용하기 위해서 음수값을 넣어주는 행동

	
	while (!que.empty() ) {
		int cost = -que.top().first; // -를 다시 붙여준다. 
		int pos = que.top().second;
	
		que.pop();

		if (result[pos] < cost) continue;
		
		for (int i = 0; i < arr[pos].size(); i++) {
			int adjacency_pos = arr[pos][i].first;
			int adjacency_cost = arr[pos][i].second;

			if (adjacency_cost + cost < result[adjacency_pos]) {
				result[adjacency_pos] = adjacency_cost + cost;
				que.push(make_pair(-result[adjacency_pos], adjacency_pos));
			}

		}
		
		
	}
	
	

}

int main() {

	int u, vv, w;
	
	cin >> v >> e >> k;
	

	for (int i = 0; i < e; i++) {
		cin >> u >> vv >> w;
		arr[u].push_back(make_pair(vv, w));
	}

	solution();
	
	for (int i = 1; i < result.size(); i++) {
		if (i == k)
			cout << 0 << '\n';
		else if (result[i] == 123456789)
			cout << "INF" << '\n';
		else
			cout << result[i] << '\n';
	}
	


	return 0;
}

우선순위 큐는 일반 큐와는 다르게  트리구조입니다.

그리고 현재 저장된 값들 중 최댓값 혹은 최솟값을 내놓습니다.

그렇기 떄문에 삽입, 삭제 할 때 시간복잡도는 O(logN) 입니다.

<사용 함수>
push(X) // 우선순위 큐에 새로운 값을 추가

top() // 우선순위 큐의 루트 노드 리턴

pop() // 우선순위 큐에서 루트 노드를 삭제

size() // 우선순위 큐 내에 포함된 원소들의 수를 리턴

empty() // 우선순위 큐가 empty이면 true를 리턴

우선순위 큐 중 최댓값을 내놓는 것을 Max 힙, 최솟값을 내놓는 것을 Min 힙이라고 부릅니다.

Max 힙을 사용

1. priority_queue< int, vector<int> > q;
2. priority_queue< int, vector<int>, less<int> > q; 

* less 의미가 Max 힙의 의미와 헷갈릴 수 있으니 주의

3. 전달할 데이터가 2개 이상이면 다음과 같이 pair로 묶는다.

priority_queue< pair<int,int> > pq;

Min 힙을 사용

1. priority_queue< int, vector<int>, greater<int> > q;

2. 혹은 priority_queue< int, vector<int> > q;를 쓰고 push(-X) & -top() 같이 사용 가능.

3. 전달할 데이터가 2개 이상이면 다음과 같이 pair로 묶는다.

priority_queue< pair<int,int> > pq;를 쓰고 push(-X) & -top() 같이 사용 가능.

pair로 묶었다면 .first 값을 1순위로 값을 뽑아내고 그다음 .second 값을 2순위

pair< int,pair<int,int> > 형태는 .first 1순위 .second.first 2순위 .second.second 3순위

그리고 sort함수와 동일하게 사용자가 직접 함수를 생성해서 우선순위를 구분해줄 수도 있습니다.

그건 다른 포스팅에서 올리도록 하겠습니다. 

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

dfs문제이고 백트래킹에서 대표적인 문제입니다.

15X15체스판까지 가능합니다. 

하지만 dfs 구현시 함수에서 NxN번 반복하면 당연히 시간초과입니다.  

다른방법을 생각해야합니다.

퀸은 자기의 양옆과 대각선 모두 이동이 가능합니다. 즉 행단위로 검사해도 괜찮습니다. 어차피 퀸이 있는 행에는 퀸이 있을 수 없기떄문입니다. 그렇기 때문에 열값은 count값을 사용합니다. ( 퀸이 체스판에 있을때마다 1씩증가)

n=4라면 답은 2입니다.

0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

우선 정답코드입니다.

#include <iostream>
using namespace std;

int n = 0, result  = 0;
bool visited[15][15] = { 0 };

bool available(int i, int cnt) {

	int x, y;
	for (x = 0; x < cnt; x++) {
		if (visited[i][x]) return false;
	}

	for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
		if (visited[y][x]) return false;
	}

	for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
		if (visited[y][x]) return false;
	}

	return true;
}

void dfs(int cnt) {

	if (cnt == n) {
	
		result++;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i][cnt] && available(i, cnt)) {

			visited[i][cnt] = 1;
			dfs(cnt + 1);
			visited[i][cnt] = 0;
		}
	}

	

}
int main(){

	cin >> n;

	dfs(0);
		
	cout << result << endl;

	return 0;
}

아래가 재귀루트입니다.

for (int i = 0; i < n; i++) {
		if (!visited[i][cnt] && available(i, cnt)) {

			visited[i][cnt] = 1;
			dfs(cnt + 1);
			visited[i][cnt] = 0;
		}
	}

행은 0~n-1 까지 이동하며 검사하고 열값은 체스판에 퀸을 올려놓을때 마다 1씩증가하며 위치를 찾습니다. 

아래는 검사함수입니다.

bool available(int i, int cnt) {

	int x, y;
	for (x = 0; x < cnt; x++) {
		if (visited[i][x]) return false;
	}

	for (x = cnt - 1, y = i - 1; y >= 0; x--, y--) {
		if (visited[y][x]) return false;
	}

	for (x = cnt - 1, y = i + 1; y < n; x--, y++) {
		if (visited[y][x]) return false;
	}

	return true;
}

자신의 왼쪽에 퀸이 있는지 확인하는 과정입니다. 

9:30 에 시작했습니다.

철저하게 온도체크를 하고 웰컴키트를 나눠주셨습니다.

베라 아이스크림 케잌 기프티콘, 간식, 펜, 마스크, 공책 등을 나눠주셨습니다.

이후 입소식을 가지고 기숙사에 들렀습니다. 

2인 1실이고 방이 넓어서 놀랐습니다. 

오후에는 직무 공통 교육이 이뤄졌습니다. 

행복은 결과가 아닌 과정이라는 말이 인상적이었습니다.

교육을 들으며 스스로에 대해서 생각해볼 수 있어서 좋았습니다.

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

단순한 구현문제였습니다.

브론즈문제가 왜 정답률이 20퍼인지 의아했는데 몇가지 함정이 있더군요

%10을 할 경우 10이 0으로 출력될 수 있는 함정과 

108^1 과 같은 값이 해당 숫자 그대로 출력 될 수 있는 함정이 있습니다.

정답코드입니다.

#include <iostream>
using namespace std;
int t = 0;
int a = 0, b = 0;

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


	cin >> t;
	while (t--) {
		long long result = 1;
		cin >> a >> b;
		result = a;
		for (int i = 0; i < b - 1; i++) {
			result *= a;
			result %= 10;
		}
		result %= 10;
		if (result == 0)
			cout << 10 << "\n";
		else
			cout << result << "\n";
	}
}

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

BFS, DFS 문제입니다! 근데 이 문제는 DFS 풀이법을 허용하지 않았습니다. 

최단거리를 구할때는 BFS를 사용하는 습관을 가져야겠습니다.

기본적인 BFS문제입니다. 기존에는 4방향으로 이동하지만 6방향으로  이동한다는 차이점만 있습니다. 

토마토 6방향문제와 동일한 문제입니다.

너무 일반적인 문제라 설명은 생략하겠습니다.

정답코드입니다.

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

int l = 0, r = 0, c = 0;
int result;
char arr[31][31][31];
int visited[31][31][31];
int y_ar[6] = { 0, 0, 1, -1, 0, 0 };
int x_ar[6] = { 0, 0, 0, 0, 1, -1 };
int z_ar[6] = { 1, -1, 0, 0, 0, 0 };



void bfs(int sz,int sy,int sx) {
	
	queue <int> que[3];
	que[0].push(sz);
	que[1].push(sy);
	que[2].push(sx);
	visited[sz][sy][sx] = 1;
	while (que[0].empty() != 1) {


		int zz = que[0].front();
		int yy = que[1].front();
		int xx = que[2].front();
		que[0].pop(), que[1].pop(), que[2].pop();
		
		for (int i = 0; i < 6; i++) {
			int z = zz + z_ar[i];
			int y = yy + y_ar[i];
			int x = xx + x_ar[i];

			if (z >= 0 && z < l && y >= 0 && y < r && x >= 0 && x < c)
				if (visited[z][y][x] == 0 && arr[z][y][x] != '#') {
					visited[z][y][x] = visited[zz][yy][xx] + 1;
					que[0].push(z);
					que[1].push(y);
					que[2].push(x);
				}
		}
	}

	for (int i = 0; i < l; i++)
		for (int j = 0; j < r; j++)
			for (int k = 0; k < c; k++)
				if (arr[i][j][k] == 'E')
					result = visited[i][j][k];



}

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

	while (1) {
		cin >> l >> r >> c;
		if (l == 0 && r == 0 && c == 0)
			break;

		memset(visited, 0, sizeof(visited));

		result = (int)2e9;
		int sz, sy, sx;

		for (int i = 0; i < l; i++)
			for (int j = 0; j < r; j++) {
				cin >> arr[i][j];

				for (int k = 0; k < c; k++) {
					if (arr[i][j][k] == 'S')
						sz = i, sy = j, sx = k;
				}
			}
	
		bfs(sz, sy, sx);
		

		if (result == 0)
			cout << "Trapped!" <<"\n";
		else
			cout << "Escaped in " << result  - 1<< " minute(s)." <<"\n";
	}

	return 0;
}