이것 저것 &

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

접근방식

1. 간만에 어려웠던 문제... 동작 자체는 쉽지만 시간초과, 메모리 초과때문에 삽질을 너무 많이했슴니다

2. 일반적인 얼음 녹이기, bfs를 사용하게 되며 매번 1500X1500짜리 필드를 탐색해주어야 하기때문에

O(1500*1500*cnt)로 당연히 시간 초과...

3. 이미 탐색한 영역은 넘어가고 새로운 영역만 bfs를 통해서 탐색할 수 있도록 구현하는 것이 핵심

문제풀이 

1. 백조하나를 기준으로 bfs를 진행함. 이때 다음번에 녹을 얼음을 임시큐에 저장해두었다가 bfs에서 사용하는 큐에 저장한다.

이렇게 행동함으로서 매번 bfs에는 새로 녹은 지점에만 탐색을 할 수 있도록 만드는 것이다. 

2. bfs이후에는 얼음을 녹이는 작업을 진행함. 기존 물좌표들은 pop으로 큐에서 빼고 얼음에서 물로 변한 위치들만 다시 큐로 넣어주는 방식이다 

아래는 정답코드!

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

typedef struct a {
	int y, x;
}dir;

dir ar[4] = { {1,0},{0,1},{-1,0},{0,-1} };

int r, c;
string arr[1500]; // 0 base
vector <dir> swan; // swan
queue <dir> vec; //water

queue <dir> q;
bool visited[1500][1500] = { 0, };


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

	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> arr[i];
		for (int j = 0; j < c; j++) {
			if (arr[i][j] == 'L') {
				arr[i][j] = '.';
				swan.push_back({ i, j });
			}
			if (arr[i][j] == '.')
				vec.push({ i,j });
		}
	}

	q.push({ swan[0].y,swan[0].x });
	visited[swan[0].y][swan[0].x] = 1;

	for (int cnt = 0;; cnt++) {
		queue <dir> nq; //다음 단계 큐에 포함되는 값 

		bool flag = 0;
		while (!q.empty()) {
			int y = q.front().y;
			int x = q.front().x;
			q.pop();

			if (y == swan[1].y && x == swan[1].x) {
				flag = 1;
				break;
			}

			for (int i = 0; i < 4; i++) {
				int ny = y + ar[i].y;
				int nx = x + ar[i].x;
				if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx])
					continue;

				visited[ny][nx] = 1;
				if (arr[ny][nx] == 'X')
					nq.push({ ny,nx });
				else if (arr[ny][nx] == '.') {
					q.push({ ny , nx });
				}
			}
		}


		if (flag) {
			cout << cnt << endl;
			return 0;
		}

		q = nq;

		int ws = vec.size();
		while (ws--) {

			int y = vec.front().y;
			int x = vec.front().x;
			vec.pop();

			for (int i = 0; i < 4; i++) {
				int ny = y + ar[i].y;
				int nx = x + ar[i].x;

				if (ny < 0 || ny >= r || nx < 0 || nx >= c )
					continue;
				if (arr[ny][nx] == 'X') {
					arr[ny][nx] = '.';
					vec.push({ ny,nx });
				}
			}



		}


	}

	return 0;
}

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

접근방식

1. 문제를 이해하는게 힘들었던 문제..;;

3. 결국 탐색을 통해서 동영상마다 유사도를 저장해주고 문제를 해결하면 되는 문제

4. 우선순위 큐를 사용한 탐색을 고안(굳이 우선순위일 필요가 없을 것 같긴하다)

문제풀이 

1. 우선순위큐를 사용하여 동영상별로 유사도를 도출. dist배열에 저장

코드를 직접 확인하는게 더 빠를 것 같음

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

int n, q;
int a, b, c;
int k, v;
vector <pair<int, int>> vec[5001];
int dist[5001][5001];

void dijkstra(int num) {
	queue <pair<int,int>> que;
	que.push(make_pair(num,2000000000));
	
	while (!que.empty()) {

		int cur = que.front().first;
		int cost = que.front().second;
		que.pop();

		for (int i = 0; i < vec[cur].size(); i++) {
			
			if (dist[num][vec[cur][i].first] != 2000000000)
				continue;
			if (vec[cur][i].second > cost) {
				dist[num][vec[cur][i].first] = cost;
				que.push(make_pair(vec[cur][i].first, cost));
			}
			else {
				dist[num][vec[cur][i].first] = vec[cur][i].second;
				que.push(make_pair(vec[cur][i].first, vec[cur][i].second));
			}

		}


	}

}

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

	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;
		vec[a].push_back(make_pair(b, c));
		vec[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			dist[i][j] = 2000000000;
		dijkstra(i);
	}

	for (int i = 0; i < q; i++) {
		cin >> k >> v;
		int cnt = 0;
	
		for (int j = 1; j <= n; j++) {
			if (j == v)
				continue;
			if (dist[v][j] >= k)
				cnt++;
		}
		cout << cnt << "\n";
	}

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

	return 0;
}

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

전형적인 dp문제

접근방식

1. dp를 사용해서 문제를 해결

dp[n] = max(dp[n], cost)

만약 이전 dp값과 합칠 수 있다면  --- temp = min(dp2[j - arr[i][0]], arr[i][1])

dp[j] = max(dp[j], temp); 

2. 메모리가 생각보다 크다. 이차원 배열로 풀지 말고 before dp 배열을 하나 만들어서 이전 값과 비교해주면서 진행!

문제풀이 

1. dp!

2. 두 점화식을 구현!

아래는 정답코드입니다.

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

int d, p;

int dp[100001];
int dp2[100001];
int arr[351][2];
int temp = 0;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> d >> p;
	for (int i = 1; i <= p; i++) 
		cin >> arr[i][0] >> arr[i][1];
	
	for (int i = 1; i <= p; i++) {
		for (int j = 1; j <= d; j++) {
			if (j == arr[i][0])
				dp[j] = max(dp[j], arr[i][1]);
			
			if (j > arr[i][0]) {
				if (dp2[j - arr[i][0]] != 0) {
					temp = min(dp2[j - arr[i][0]], arr[i][1]);
					dp[j] = max(dp[j], temp);
				}
			}
		}

		for (int j = 1; j <= d; j++) {
			//cout << dp[j] << ' ';
			dp2[j] = dp[j];
		}
		//cout << endl;
	}

	cout << dp[d] << endl;
	return 0;
}

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

골드4인걸 보면 어려운 부분이 있는것 같지만.. 그냥 일반적인 BFS로 해결할 수 있는 문제 

접근방식

1. 일반적인 BFS를 통해서 도달이 가능한지 확인할 수 있다.

문제풀이 

1. vector에 좌표를 표시

2. bfs!

아래는 정답코드입니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
bool visited[201] = { 0, };
vector <int> vec[201];
int arr[1001] = { 0, };

void bfs() {
	queue <int> que;
	que.push(arr[0]);
	visited[arr[0]] = 1;

	while (!que.empty()) {
		int pos = que.front();
		que.pop();

		for (int i = 0; i < vec[pos].size(); i++) {
			int npos = vec[pos][i];
			if (visited[npos] == false) {
				visited[npos] = 1;
				que.push(npos);
			}

		}

	}

}

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

	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			int temp;
			cin >> temp;
			if (temp) {
				vec[i].push_back(j);
				vec[j].push_back(i);
			}
		}

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

	bfs();

	for (int i = 0; i < m; i++)
		if (visited[arr[i]] == false) {
			cout << "NO" << endl;
			return 0;
		}

	cout << "YES" << endl;
	return 0;
}

문제풀이: www.acmicpc.net/problem/19238

구현 순서는 

• 0. 입력값 받기
• 1. bfs로 이동거리 재기
• 2. 가장 가까운 사람에게 이동
• 3. 목적지까지 거리 도출
• 4. 목적지로 이동

주의할 점은

• 1. 이동과 동시에 도착할때, 즉 택시위치와 사람위치가 같은 경우에는 거리가 0이다.
• 2. 벽으로 막혀있어 택시가 목적지나 사람에게 도달하지 못해도 결과값은 -1이다.
• 3. 목적지에 도착하면서 연료가 바닥나는 것은 괜찮다.

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

typedef struct a {
	int y;
	int x;
}pos;

int n, m, f;
int arr[21][21] = { 0, };
int visited[21][21];
pos taxi;
vector <pos> people;
vector <pos> destination;

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

void bfs(int y, int x) {
	queue <pair<int, int>> que;
	que.push(make_pair(y, x));
	visited[y][x] = 1; // -1 해야함 

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= n) {
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = visited[cy][cx] + 1;
				}
			}
		}
	}
}

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

	cin >> n >> m >> f;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> arr[i][j];
	cin >> taxi.y >> taxi.x;
	for (int i = 0; i < m; i++) {
		int t1, t2, t3, t4;
		cin >> t1 >> t2 >> t3 >> t4;
		people.push_back({ t1,t2 });
		destination.push_back({ t3,t4 });
	}

	for (int k = 0; k < m; k++) {
		//1. 이동 거리 측정
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		/*
		for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
		cout << visited[i][j] << ' ';
		cout << endl;
		}*/

		//2. 가장 가까운 사람 선택
		int dis = 1000000000;
		int ny = 0, nx = 0, index = -1;
		for (int i = 0; i < people.size(); i++) {
			int y = people[i].y;
			int x = people[i].x;
			if (visited[y][x] < dis) {
				ny = y;
				nx = x;
				index = i;
				dis = visited[y][x];
			}
			else if (visited[y][x] == dis) {
				if (ny > y) {
					ny = y;
					nx = x;
					index = i;
				}
				else if (nx > x && ny == y) {
					ny = y;
					nx = x;
					index = i;
				}
			}
		}
		people.erase(people.begin() + index);
		taxi.y = ny, taxi.x = nx;
		f -= (visited[ny][nx] - 1);
		if (visited[ny][nx] == 0) {
			f = -1;
			break;
		}
		if (f <= 0)
			break;
		//cout << "y " << ny << "x " << nx << "i " << index << endl;

		//3. 목적지까지 거리 도출
		memset(visited, 0, sizeof(visited));
		bfs(taxi.y, taxi.x);
		//4. 목적지로 이동 
		int dy = destination[index].y;
		int dx = destination[index].x;
		if (visited[dy][dx] == 0) {
			f = -1;
			break;
		}
		taxi.y = dy, taxi.x = dx;
		destination.erase(destination.begin() + index);
		f -= (visited[dy][dx] - 1);
		if (f < 0)
			break;
		f += ((visited[dy][dx] - 1) * 2);
	}


	if (f <= 0)
		cout << -1 << endl;
	else
		cout << f << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/1697

너무나도 간단한 bfs 문제입니다.

숫자 범위가 크기 때문에 bfs를 선택했고, 방문여부를 판단하는 배열을 만들어서 문제를 해결했습니다.

아래는 정답 코드입니다.

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

int n = 0, k = 0;
int result = 0;
int visited[100001] = { 0, };
queue <int> que;

int main() {
	iostream::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;

	que.push(n);
	visited[n] = 1;
	while (!que.empty()) {
		int p = que.front();
		que.pop();
		if (p == k) {
			cout << visited[p] - 1 << endl;
			return 0;
		}
		if (visited[p - 1] == 0 && (p - 1) >= 0 && (p - 1) <= 100000)
			que.push(p - 1), visited[p - 1] = visited[p] + 1;
		if (visited[p + 1] == 0 && (p + 1) >= 0 && (p + 1) <= 100000)
			que.push(p + 1), visited[p + 1] = visited[p] + 1;
		if (visited[p*2] == 0 && (p*2) >= 0 && (p*2) <= 100000)
			que.push(p*2), visited[p*2] = visited[p] + 1;
	}

	return 0;
}

문제링크:www.acmicpc.net/problem/2606

기본적인 bfs, dfs 문제입니다.

vector를 통해서 양방향 그래프를 구현하고 완전탐색을 통해서 연결된 갯수를 파악하면 되는 문제입니다.

기본중에 기본문제입니다. 

이제 알고리즘을 입문하시는 분들이라면 그냥 코드자체를 외우듯이 이해하시면 될 것 같습니다.

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

int n = 0, m = 0, result = 0;
vector <int> vec[101];
bool visited[101] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int t1, t2;
		cin >> t1 >> t2;
		vec[t1].push_back(t2);
		vec[t2].push_back(t1);

	}

	queue <int> que;
	visited[1] = 1;
	que.push(1);

	while (!que.empty()) {
		int num = que.front();
		que.pop();

		for (int i = 0; i < vec[num].size(); i++) {
			int next = vec[num][i];
			if (visited[next] == 1) continue;
			que.push(next);
			visited[next] = 1;
			result++;
		}
	}

	cout << result << endl;
	return 0;
}

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

bfs문제인데 조금 꼬아놓은 bfs였습니다! 

최단 경로이동이 아니라 벽을 최소로 부수며 이동할때의 벽을 최소 몇 개 부수어야 하는지이기 때문에 방문 배열이 총 2개가 필요합니다.

1. 방문했는지 여부를 판단해주는 배열

2. 방문했다면 해당 경로로 최소 몇번만에 도달할 수 있는 표시하는 배열

쉬운문제였기 때문에 바로 정답코드입니다.

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

int m, n;
int arr[101][101] = { 0, };
int visited[101][101][2] = { 0, };

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

void bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(1, 1));
	if (arr[1][1] == 1) visited[1][1][0] = 1, visited[1][1][1] = 1;
	else visited[1][1][0] = 1, visited[1][1][1] = 0;

	while (!que.empty()) {

		int yy = que.front().first;
		int xx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int y = yy + y_ar[i];
			int x = xx + x_ar[i];

			if (y >= 1 && y <= n && x >= 1 && x <= m) {
				if (visited[y][x][0] == 0) { //방문한적 없어
					visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
					que.push(make_pair(y, x));	
				}
				else { // 방문했다면, 
					if (visited[y][x][1] > (visited[yy][xx][1] + arr[y][x])) { 
						visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
						que.push(make_pair(y, x));
					}
					

				}
			}

		}

	}

}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++){
			string temp;
			cin >> temp;
			for (int j = 1; j <= m; j++)
				arr[i][j] = temp.at(j - 1) - '0';
	}

	
	bfs();

	
	cout << visited[n][m][1] << "\n";
}

 visited[yy][xx][1] + arr[y][x]는 지금까지 벽을 부순횟수 더하기 현재 벽이 있다면 부수고 들어가고(+1) 아니면(+0)을 하는 코드입니다.