언제나 처음처럼

[문제 링크]

 먼저 입력으로 주어지는 건설 순서대로 그래프를 만든다. 필자는 역순으로 탐색할 계획이었기 때문에 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

[문제 링크]

원소가 L인 좌표를 시작점으로 하는 너비 우선 탐색을 수행하면 해당 좌표에서 가장 멀리 떨어진 'L'의 거리를 알 수 있다.

원소가 L인 모든 좌표에 대하여 너비 우선 탐색을 수행하고 그중 최댓값을 출력하면 원하는 결과를 얻을 수 있다.

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

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int R, C;
char board[50][50];
bool visited[50][50];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

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

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

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

			if (there.y >= 0 && there.y < R && there.x >= 0 && there.x < C)
				if (!visited[there.y][there.x] && board[there.y][there.x] == 'L') {
					visited[there.y][there.x] = true;
					q.push({ there, nextDist });
				}
		}
	}

	return ret;
}

int bfsAll() {
	int ret = 0;

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'L') {
				memset(visited, false, sizeof(visited));
				ret = max(ret, bfs({ i,j }));
			}
		}

	return ret;
}

int main(void) {
	cin >> R >> C;

	for (int i = 0; i < R; i++)
		for (int j = 0; j < C; j++)
			cin >> board[i][j];

	cout << bfsAll() << endl;

	return 0;
}

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

[문제 링크]

모든 나라를 방문할 때 까지 너비 우선 탐색을 통해 인구수 차이가 L이상 R이하인 나라들을 연합국가로 묶는다.

그다음 문제에 명시된대로 (연합 인구수 / 연합 국가수) 만큼의 인구로 인구 이동을 시킨다.

인구 이동이 없을 때 까지 위 과정을 반복하면 원하는 결과를 얻을 수 있다.

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

struct Pos {
	int y;
	int x;
};

vector<vector<int>> board(50, vector<int>(50, 0));
bool visited[50][50];
int N, L, R;
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int getCountryDifference(int a, int b) {
	if (a > b) return a - b;
	else return b - a;
}

vector<Pos> bfs(Pos start) {
	vector<Pos> ret;
	ret.push_back(start);

	queue<Pos> q;
	q.push(start);
	visited[start.y][start.x] = true;

	while (!q.empty()) {
		Pos here = q.front();
		int population = board[here.y][here.x];
		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 (!visited[there.y][there.x]) {
					int nextPopulation = board[there.y][there.x];
					int diff = getCountryDifference(population, nextPopulation);

					if (diff >= L && diff <= R) {
						visited[there.y][there.x] = true;
						ret.push_back(there);
						q.push(there);
					}
				}
		}
	}

	return ret;
}

bool bfsAll() {
	vector<vector<int>> temp;
	temp = board;

	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				vector<Pos> isUnion = bfs({ i,j });
				int cnt = isUnion.size();
				int sum = 0;
				for (int k = 0; k < cnt; k++)
					sum += board[isUnion[k].y][isUnion[k].x];
				for (int k = 0; k < cnt; k++)
					temp[isUnion[k].y][isUnion[k].x] = sum / cnt;
			}
		}

	if (temp == board)
		return true;
	else {
		board = temp;
		return false;
	}
}

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

	int result = 0;
	while (!bfsAll()) {
		memset(visited, false, sizeof(visited));
		result++;
	}

	cout << result << endl;

	return 0;
}

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

[문제 링크]

시작지점(1,1) 에서 도착지점(N,M) 으로 가는 최단 경로를 구하는 문제였다.

벽을 최대한 안부시는 경로로 이동해야 하기 때문에 방문표시를 하면 안된다.

따라서, 다익스트라 알고리즘을 이용하여 구현하였다.

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

const int INF = 987654321;
int N, M;
char board[101][101];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int dijkstra() {
	vector<vector<int>> dist(101, vector<int>(101, INF));
	dist[1][1] = 0;

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push({ 0, {1,1} });

	while (!pq.empty()) {
		int hy = pq.top().second.first;
		int hx = pq.top().second.second;
		int isBreak = -pq.top().first;
		pq.pop();

		if (dist[hy][hx] < isBreak) continue;

		for (int i = 0; i < 4; i++) {
			int ny = hy + dy[i];
			int nx = hx + dx[i];

			if (ny > 0 && ny <= N && nx > 0 && nx <= M) {
				int nextBreak = isBreak + board[ny][nx] - '0';

				if (dist[ny][nx] > nextBreak) {
					dist[ny][nx] = nextBreak;
					pq.push({ -nextBreak, {ny, nx} });
				}
			}
		}
	}

	return dist[N][M];
}

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

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			cin >> board[i][j];

	cout << dijkstra() << endl;

	return 0;
}

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

[문제 링크]

입력으로 주어지는 순열과 1, 2, 3, ... N 순열은 서로 1:1 대응이라는 것을 알 수 있다.

따라서 입력받는 순서대로 1부터 N까지 정점을 연결한 다음, 모든 정점을 방문할 때 까지 dfs를 수행한 횟수를 출력하면 원하는 결과를 얻을 수 있다.

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

vector<int> adj(1001); // 1:1 그래프
vector<bool> visited(1001);

void dfs(int here) {
	visited[here] = true;
	int there = adj[here];
	if (!visited[there]) dfs(there);
}

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

	while (tc--) {
		int N;
		cin >> N;
		visited = vector<bool>(N + 1, false);

		for (int i = 1; i <= N; i++) {
			int num;
			cin >> num;
			adj[i] = num;
		}

		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				cnt++;
				dfs(i);
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

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

[문제 링크]

 문제를 해결하기 위해 4가지 과정을 반복하였다.

1) iceMelt() 함수를 통해 빙산 주변에 있는 물의 수만큼 빙산을 녹인다.

2) 빙산이 2개 이상으로 나뉘어져 있는지 확인하기 위해 isSeparate() 함수를 정의하고, dfs() 를 통해 한 덩어리에 속한 빙산을 방문한다.

3)  만약 dfs()를 수행할 빙산이 없다면 모두 녹았다는 의미로 2를 반환한다.

4) dfs()를 수행했는데 아직 방문하지 않은 빙산이 있다면 분리되었다는 의미인 1을 반환하고, 모두 방문했다면 2개 이상으로 분리되지 않았다는 의미인 0을 반환한다.

isSeparate() 이 0을 반환했다면 위 과정을 다시 수행하고, 1을 반환했다면 누적한 시간을 출력, 2를 반환했다면 0을 출력한다.

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

struct Pos {
	int y;
	int x;
};

int N, M;
int board[300][300];
bool visited[300][300];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

void dfs(Pos here) {
	visited[here.y][here.x] = true;

	for (int i = 0; i < 4; i++) {
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];
		if (ny >= 0 && ny < N && nx >= 0 && nx < M)
			if (!visited[ny][nx] && board[ny][nx] != 0)
				dfs({ ny, nx });
	}
}

int isSeparate() {
	memset(visited, false, sizeof(visited));

	bool check = false;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] != 0 && !visited[i][j]) {
				if (!check) {
					dfs({ i, j });
					check = true;
				}
				else 
					return 1;
			}

	if (!check) 
		return 2;
	else 
		return 0;
}

void iceMelt() {
	int temp[300][300];
	memcpy(temp, board, sizeof(board));

	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++) {
			if (temp[i][j] != 0) {
				int water = 0;
				for (int k = 0; k < 4; k++) {
					int ny = i + dy[k];
					int nx = j + dx[k];
					if (ny >= 0 && ny < N && nx >= 0 && nx < M)
						if (temp[ny][nx] == 0) water++;
				}
				board[i][j] -= water;
				if (board[i][j] < 0) board[i][j] = 0;
			}
		}
}

int solution() {
	int years = 0;
	int separate = isSeparate();

	while (separate == 0) {
		years++;
		iceMelt();
		separate = isSeparate();
	}

	if (separate == 1)
		return years;
	else
		return 0;
}

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

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

	cout << solution() << endl;

	return 0;
}

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

[문제 링크]

입력받는 버스 노선은 시작정점, 도착정점, 비용으로 이루어져 있다. 시작정점과 도착정점이 명시되어 있기 때문에 필자는 그래프를 무향그래프가 아닌 방향그래프로 만들었다.

또한 같은 노선이 여러개 존재할 수 있다고 명시되어 있기 때문에 이미 연결된 노선과 같은 노선이 입력으로 들어오면 기존 노선의 비용과 비교하여 더 적은 비용을 노선으로 선택하도록 구현하였다.

그래프를 만든 다음 플로이드-와샬 알고리즘을 수행하고 결과를 출력해주면 정답을 받을 수 있다.

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

const int INF = 987654321;
int n, m;
vector<vector<int>> adj(101, vector<int>(101, INF));

void floyd() {
	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) {
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (adj[a][b] == INF)
			adj[a][b] = c;
		else
			adj[a][b] = min(adj[a][b], c);
	}

	floyd();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (adj[i][j] == INF)
				cout << 0 << ' ';
			else
				cout << adj[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

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