언제나 처음처럼

[문제 링크]

원소가 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

[문제 링크]

입력으로 주어지는 문자열 H와 H의 모든 부분문자열 N에 대해 KMP-search 를 수행하여 H에 N과 일치하는 문자열이 2개 이상 존재하는 N 중에서 길이가 가장 긴 부분문자열의 길이를 출력해주면 된다.

다만, 부분문자열 N의 길이를 1에서부터 시작하면 시간이 너무 오래걸리므로, 이분탐색을 활용하여 시간복잡도를 줄였다. (그래도 오래 걸리는건 함정;;)

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

vector<int> getPartialMatch(string& N) {
	int Nlen = N.length();
	vector<int> pi(Nlen, 0);

	int begin = 1, matched = 0;
	while (begin + matched < Nlen) {
		if (N[begin + matched] == N[matched]) {
			matched++;
			pi[begin + matched - 1] = matched;
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return pi;
}
bool KMP_search(string& H, string& N) {
	int Hlen = H.length(), Nlen = N.length();
	vector<int> pi = getPartialMatch(N);
	int cnt = 0;

	int begin = 0, matched = 0;
	while (begin <= Hlen - Nlen) {
		if (matched < Nlen && H[begin + matched] == N[matched]) {
			matched++;
			if (matched == Nlen) {
				cnt++;
				if (cnt == 2) return true;
			}
		}
		else {
			if (matched == 0)
				begin++;
			else {
				begin += matched - pi[matched - 1];
				matched = pi[matched - 1];
			}
		}
	}

	return false;
}

int allPartialStrSearch(string str) {
	int ret = 0;
	int len = str.length();

	int start = 1, end = len;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (mid == 0) break;

		for (int i = 0; i + mid <= len; i++) {
			string N = str.substr(i, mid);
			if (KMP_search(str, N)) {
				ret = mid;
				start = mid + 1;
				break;
			}
		}
		if (start != mid + 1)
			end = mid - 1;
	}

	return ret;
}

int main(void) {
	string str;
	cin >> str;

	cout << allPartialStrSearch(str) << endl;

	return 0;
}

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

[문제 링크]

단순히 위, 왼쪽, 오른쪽, 아래 순으로 탐색하다가 먹을 수 있는 물고기가 발견되면 그 물고기가 문제 조건에 맞는 물고기라 생각하고 풀었다가 고생한 문제였다.

그래서 현재 상태에서 먹을 수 있는 물고기들의 위치를 모두 우선순위큐에 담은 다음 가장 우선순위가 높은 물고기를 먹는 방식으로 구현하여 정답을 받을 수 있었다.

bfs를 계속 반복하면서 물고기를 먹다가 만약 bfs를 했는데 우선순위큐가 비어있다면 맵에 먹을 수 있는 물고기가 없는 것이므로 반복을 종료하고 그동안 움직인 횟수를 출력하면 원하는 결과를 얻을 수 있다.

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

struct Shark {
	int y;
	int x;
	int level;
	int exp;
	int move;

	// 물고기를 먹는다.
	// 경험치가 레벨과 같아지면 레벨업
	void eatFish() {
		exp++;
		if (level == exp) {
			level++;
			exp = 0;
		}
	}
};

// priority_queue 크기 비교를 위한 연산자 오버로딩
bool operator< (const Shark& lhs, const Shark& rhs) {
	if (lhs.move > rhs.move)
		return true;
	else if (lhs.move == rhs.move && lhs.y > rhs.y)
		return true;
	else if (lhs.move == rhs.move && lhs.y == rhs.y && lhs.x > rhs.x)
		return true;

	return false;
}

Shark shark;
int N;
int board[20][20];
// 문제 조건에 따라 북 서 동 남 순으로 탐색
int dy[4] = { -1, 0, 0, 1 };
int dx[4] = { 0, -1, 1, 0 };

bool bfs() {
	vector<vector<bool>> visited(20, vector<bool>(20, false));
	visited[shark.y][shark.x] = true;

	queue<Shark> q;
	q.push(shark);

	// 먹이로 가능한 좌표를 우선순위가 큰 순서대로 저장
	priority_queue<Shark> pq;

	while (!q.empty()) {
		Shark here = q.front();
		int fish = board[here.y][here.x];
		q.pop();

		if (fish != 0 && fish < here.level) {
			pq.push(here);
			continue;
		}

		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 < N)
				if (!visited[ny][nx] && board[ny][nx] <= here.level) {
					visited[ny][nx] = true;
					q.push({ ny, nx, here.level, here.exp, here.move + 1 });
				}
		}
	}

	if (!pq.empty()) {
		Shark pick = pq.top();
		board[pick.y][pick.x] = 0;
		shark = pick;
		shark.eatFish();
		return true;
	}

	return false;
}

int main(void) {
	cin >> N;

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

			if (board[i][j] == 9) {
				board[i][j] = 0;
				shark = { i, j, 2, 0, 0 };
			}
		}
	while (1) if (!bfs()) break;
	
	cout << shark.move << endl;

	return 0;
}

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