언제나 처음처럼

[문제 링크]

너비 우선 탐색으로 풀 수 있는 문제였다.

먼저 크기가 10000인 prime 배열을 선언하고, 에라토스테네스의 체 알고리즘을 통해 소수가 아닌 숫자들을 true로 바꿔주었다.

그다음 문제 조건에 따라 너비 우선 탐색을 통해 A의 숫자를 한개씩 바꾸면서 숫자 B와 일치할 때까지 바꾼 최소 횟수를 구해주면 된다.

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

bool prime[10000];
bool visited[10000];

void getPrime() {
	prime[1] = true;

	for (int i = 2; i < 10000 / 2; i++) {
		if (prime[i]) continue;

		for (int j = i * 2; j < 10000; j += i)
			if (!prime[j]) 
				prime[j] = true;
	}
}

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

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

		if (here == b) return move;

		for (int i = 1; i <= 4; i++) {
			int there;
			switch (i) {
			case 1: // 1000의 자리
				for (int j = 1; j <= 9; j++) {
					there = (j * 1000) + (here % 1000);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 2: // 100의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 1000 * 1000) + (j * 100) + (here % 100);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 3: // 10의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 100 * 100) + (j * 10) + (here % 10);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 4: // 1의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 10 * 10) + j;
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
			}
		}
	}

	return -1;
}

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

	getPrime();

	while (tc--) {
		memset(visited, false, sizeof(visited));
		int a, b;
		cin >> a >> b;

		int result = bfs(a, b);

		if (result == -1)
			cout << "Impossible" << endl;
		else
			cout << result << endl;
	}
}

알고리즘 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

[문제 링크]

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

알고리즘은 다음과 같다.

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

[문제 링크]

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

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

#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

[문제 링크]

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

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

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