언제나 처음처럼

[문제 링크]

그래프의 오일러 서킷과 관련된 문제였다. 순환을 이루는 정점들은 서로 팀을 이루고 있다고 볼 수 있고, 순환하지 않는 정점들의 개수를 찾아주면 된다.

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

int n;
int adj[100001];
bool visited[100001];

int dfs(int here, vector<int>& circuit) {

	visited[here] = true;
	circuit.push_back(here);

	int there = adj[here];
	if (!visited[there]) {
		return dfs(there, circuit);
	}
	return there;
}

int bfs(int start, vector<int>& circuit) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		circuit.push_back(here);

		int there = adj[here];

		if (!visited[there]) {
			visited[there] = true;
			q.push(there);
		}
		else
			return there;
	}
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		memset(visited, false, sizeof(visited));
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> adj[i];

		int result = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				vector<int> circuit;
				int idx = bfs(i, circuit);
				int len = circuit.size();

				for (int i = 0; i < len; i++) {
					if (idx == circuit[i]) break;
					result++;
				}
			}
		}
		cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

간단한 문제였다. 모든 정점을 시작점으로 bfs나 dfs를 수행하여 그중 최댓값을 찾으면 정답을 받을 수 있다.

하지만 이 문제를 더 빠르게 풀 수 있는 방법이 존재한다고 한다. 

뿌리노드인 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점을 시작점으로 하여 가장 멀리 떨어진 정점까지의 거리가 곧 트리의 지름이 된다. 따라서 탐색을 2번 수행하므로 O(n) 시간에 문제를 해결할 수 있다.

자세한 증명은 구사과님의 블로그에 설명되어 있다.

https://koosaga.com/14

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

int N;
vector<vector<pair<int, int>>> adj(10001);
bool visited[10001];

pair<int, int> bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	pair<int, int> ret = { 0,0 };
	while (!q.empty()) {
		int here = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (ret.second < cost)
			ret = { here, cost };

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = cost + adj[here][i].second;

			if (!visited[there]) {
				visited[there] = true;
				q.push({ there, nextCost });
			}
		}
	}

	return ret;
}


int main(void) {
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	// find maximum node
	int maxNode = bfs(1).first;

	memset(visited, false, sizeof(visited));

	// get diameter
	int diameter = bfs(maxNode).second;

	cout << diameter << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

간단한 문제처럼 보였는데 고려해줘야 할 점이 많은 문제였다.

다른 bfs 문제들을 풀듯이 D,S,L,R 4가지 경우에 대해 탐색하면서 string에 추가해주는 방식으로 구현했는데 메모리초과에 시간초과에 난리가 났다.

원인을 찾아보니 string 컨테이너의 경우 문자를 추가하는 연산이나 복사본을 큐에 집어넣는 연산에 있어 많은 시간이 필요하다고 한다.

따라서 bfs 탐색을 하면서 방문체크 대신 방문한 숫자 인덱스에 만들기 전 숫자와 어떤 버튼으로 만들었는지 정보를 원소로 담았다.

그다음 목표 숫자 B에서부터 역으로 추적하면서 어떤 버튼을 눌렀는지 vector에 담은 다음 역순으로 출력하도록 구현하였다.

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

vector<pair<int, char>> visited(10000);

int calculate(int num, char type) {
	switch (type) {
	case 'D':
		num = (num * 2) % 10000;
		break;

	case 'S':
		if (num == 0) num = 9999;
		else num -= 1;
		break;

	case 'L':
		num = (num % 1000) * 10 + (num / 1000);
		break;

	case 'R':
		num = (num % 10) * 1000 + (num / 10);
		break;
	}

	return num;
}

void Queue_push(queue<int>& q, int num, char type) {
	int nextNum = calculate(num, type);
	if (visited[nextNum].first == -1) {
		visited[nextNum].first = num;
		visited[nextNum].second = type;
		q.push(nextNum);
	}
}

void bfs(int A, int B) {
	visited = vector<pair<int, char>>(10000, { -1,-1 });
	queue<int> q;
	q.push(A);
	visited[A] = { -1, -1 };

	while (!q.empty()) {
		int hereNum = q.front();
		q.pop();

		if (hereNum == B) return;

		Queue_push(q, hereNum, 'D');
		Queue_push(q, hereNum, 'S');
		Queue_push(q, hereNum, 'L');
		Queue_push(q, hereNum, 'R');
		
	}
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		int A, B;
		cin >> A >> B;
		bfs(A, B);

		vector<char> result;
		int idx = B;
		while (idx != A) {
			result.push_back(visited[idx].second);
			idx = visited[idx].first;
		}
		
		int len = result.size();
		for (int i = len; i >= 0; i--)
			cout << result[i];
		cout << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 167 day

[문제 링크]

방향그래프를 만든 다음 최단 경로 알고리즘을 통해 간단히 풀 수 있는 문제였다.

처음 풀었을 땐 플로이드-와샬 알고리즘으로 구현해서 정답을 받았는데, 생각해보니 N이 최대 1000이기 때문에 시간복잡도가 O(N^3)인 플로이드-와샬 알고리즘을 사용하면 최악의 경우 10억만큼의 시간이 걸리게 된다. 입력데이터가 부실했기 때문에 운좋게 통과했다고 생각한다.

따라서 다익스트라 알고리즘을 사용해서 다시 구현하였다.

//추가 : 질문게시판에서 시간복잡도를 더 줄이는 방법에 대한 힌트를 발견하였다.

도착지점이 X로 정해져 있기 때문에 모든 정점의 최단 경로를 다 구할 필요 없이 정점으로 들어오는 간선들의 집합과 정점에서 나가는 간선들의 집합을 분리한 다음, 정점 X에서 들어오는 간선과 나가는 간선을 대상으로 두번의 다익스트라를 수행하면 문제를 해결할 수 있다.

// 플로이드-와샬 알고리즘 사용

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

const int INF = 987654321;
vector<vector<int>> adj(1001, vector<int>(1001, INF));

void floyd(int N) {
	for (int i = 1; i <= N; i++) {
		adj[i][i] = 0;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	int N, M, X;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A][B] = W;
	}

	floyd(N);

	int result = 0;
	for (int i = 1; i <= N; i++) {
		result = max(result, adj[i][X] + adj[X][i]);
	}

	cout << result << endl;

	return 0;
}

// 다익스트라 알고리즘 사용

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adj[1001];
vector<vector<int>> allTownDist(1001);

void dijkstra(int start) {
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

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

		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allTownDist[start] = dist;
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A].push_back({ B, W });
	}

	for (int i = 1; i <= N; i++)
		dijkstra(i);

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, allTownDist[i][X] + allTownDist[X][i]);

	cout << result << endl;

	return 0;
}

// 다익스트라 2번으로 문제를 해결하는 코드

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adjIn[1001];
vector<pair<int, int>> adjOut[1001];

vector<int> inDist(1001);
vector<int> outDist(1001);

void dijkstra(int start, int type) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	
	if (type == 1) {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjIn[here].size(); i++) {
				int there = adjIn[here][i].first;
				int nextCost = adjIn[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		inDist = dist;
	}

	else {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjOut[here].size(); i++) {
				int there = adjOut[here][i].first;
				int nextCost = adjOut[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		outDist = dist;
	}
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adjIn[A].push_back({ B, W });
		adjOut[B].push_back({ A, W });
	}

	dijkstra(X, 1); // 정점으로 들어오는 간선들의 최단경로
	dijkstra(X, 2); // 정점에서 나가는 간선들의 최단경로

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, inDist[i] + outDist[i]);

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 167 day

[문제 링크]

너비 우선 탐색을 활용하는 문제였다.

알고리즘은 다음과 같다.

1) 입력받은 배열에서 하나로 연결된 섬들을 1이 아닌 다른 숫자로 바꿔준다.

2) 배열의 모든 원소를 탐색하면서 0이 아닌 좌표를 발견하면 이 좌표를 시작점으로 하는 너비 우선 탐색을 수행한다.

3) 현재 좌표의 동서남북 방향에서 값이 0인 좌표와 (현재까지 놓은 다리 길이 + 1)을 큐에 담는다.

만약 현재 좌표에서 인접한 곳에 다른 섬이 존재한다면 두 섬이 연결된 것이므로 현재까지 놓은 다리 길이를 반환한다.

4) 0이 아닌 모든 좌표에 대해 너비 우선 탐색을 수행하면서 반환된 다리 길이 중 가장 작은 값을 결과로 출력한다.

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

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N;
int board[100][100];
bool visited[100][100];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(Pos start, int type) {
	queue<pair<Pos, int>> q;
	q.push({ start, 0 });
	visited[start.y][start.x] = true;

	while (!q.empty()) {
		Pos here = q.front().first;
		int isLen = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };

			if (there.y >= 0 && there.y < N && there.x >= 0 && there.x < N) {
				int nextType = board[there.y][there.x];

				if (!visited[there.y][there.x] && nextType == 0) {
					visited[there.y][there.x] = true;
					q.push({ there, isLen + 1 });
				}
				else if (nextType != 0 && nextType != type)
					return isLen;
			}
		}
	}

	return INF;
}

void divide_Island(Pos start, int type) {
	queue<Pos> q;
	q.push(start);
	board[start.y][start.x] = type;

	while (!q.empty()) {
		Pos here = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			
			if(there.y >= 0 && there.y < N && there.x >= 0 && there.x < N)
				if (board[there.y][there.x] == 1) {
					board[there.y][there.x] = type;
					q.push(there);
				}
		}
	}
}

int main(void) {
	cin >> N;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	int type = 2;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (board[i][j] == 1) {
				divide_Island({ i,j }, type);
				type++;
			}

	int result = INF;
	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (board[i][j] != 0) {
				memset(visited, false, sizeof(visited));
				result = min(result, bfs({ i,j }, board[i][j]));
			}
		}

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day

[문제 링크]

BFS를 통해 풀 수 있는 간단한 문제였다.

한 정점에서 이동할 수 있는 경우는 U버튼을 눌렀을 때와 D버튼을 눌렀을 때 두가지 경우이다.

따라서 두가지 경우를 큐에 담아주면서 현재 위치가 도착지점 G와 같아지는 순간의 이동 횟수를 출력하면 된다.

만약 가능한 모든 층을 다 탐색했는데 도착지점 G를 방문하지 못했다면 불가능하므로 "use the stairs"를 출력한다.

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

const int INF = 987654321;
int F, S, G, U, D;
int visited[1000001];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ S, 0 });

	while (!q.empty()) {
		int here = q.front().first;
		int press = q.front().second;
		q.pop();

		if (here == G) return press;
		
		int thereUp = here + U;

		if (thereUp <= F && !visited[thereUp]) {
			visited[thereUp] = true;
			q.push({ thereUp, press + 1 });
		}

		int thereDown = here - D;

		if (thereDown > 0 && !visited[thereDown]) {
			visited[thereDown] = true;
			q.push({ thereDown, press + 1 });
		}
	}

	return INF;
}

int main(void) {
	cin >> F >> S >> G >> U >> D;
	
	int result = bfs();

	if (result == INF)
		cout << "use the stairs" << endl;
	else 
		cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day

[문제 링크]

 먼저 입력으로 주어지는 건설 순서대로 그래프를 만든다. 필자는 역순으로 탐색할 계획이었기 때문에 X, Y 를 입력받았으면 Y정점에서 X정점으로 가는 간선을 연결하였다.

 그래프를 연결했으면 승리를 위한 건물을 시작정점으로 하는 깊이 우선 탐색을 수행하는데, 현재 정점의 건물까지 짓는데 걸리는 시간은 (현재 정점에서 건물을 짓는 시간 + 현재 정점에서 갈 수 있는 정점의 건물을 짓는데 걸리는 시간들 중 가장 큰 값) 이므로 이를 그대로 구현해주면 된다.

 추가로 이미 계산한 정점을 다시 호출하는 경우가 많으면 시간복잡도가 커지게 되므로 동적 계획법의 메모이제이션 기법을 통해 한번 계산한 정점의 최소 시간을 저장하여 중복되는 연산을 최소화해야 한다.

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

int N, K;
vector<int> adj[1001];
vector<int> weight(1001);
int memo[1001];

int dfs(int start) {
	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = 0;

	for (int i = 0; i < adj[start].size(); i++) {
		int next = adj[start][i];
		ret = max(ret, dfs(next));
	}
	ret += weight[start];

	return ret;
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		memset(memo, -1, sizeof(memo));

		for (int i = 0; i < 1001; i++)
			adj[i].clear();

		cin >> N >> K;

		for (int i = 1; i <= N; i++)
			cin >> weight[i];

		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			adj[b].push_back(a);
		}

		int W;
		cin >> W;
		
		cout << dfs(W) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 166 day

[문제 링크]

나이트의 위치를 시작점으로 하는 너비 우선 탐색을 통해 간단히 풀 수 있다.

나이트가 도착지점에 도달했을 때 그동안 움직인 횟수를 반환하도록 구현하였다.

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

struct Pos {
	int y;
	int x;
};
bool operator== (const Pos& rhs, const Pos& lhs) {
	if (rhs.y == lhs.y && rhs.x == lhs.x) return true;
	else return false;
}

int I;
int visited[300][300];
int dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };

int bfs(Pos night, Pos dest) {
	memset(visited, false, sizeof(visited));

	queue<pair<Pos, int>> q;
	q.push({ night, 0 });
	visited[night.y][night.x] = true;

	while (!q.empty()) {
		Pos here = q.front().first;
		int move = q.front().second;
		q.pop();

		if (here == dest) return move;

		for (int i = 0; i < 8; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			int nextMove = move + 1;
			
			if (there.y >= 0 && there.y < I && there.x >= 0 && there.x < I) 
				if (!visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					q.push({ there, nextMove });
				}
		}
	}
}
int main(void) {
	int tc;
	cin >> tc;

	Pos night, destination;
	while (tc--) {
		cin >> I;
		cin >> night.y >> night.x;
		cin >> destination.y >> destination.x;

		cout << bfs(night, destination) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 166 day