언제나 처음처럼

[문제 링크]

어떤 문제를 풀기 위해서 먼저 풀어야 하는 문제가 있다고 한다. 이때 어떤 문제는 먼저 풀어야 하는 문제에 의존적이라고 할 수 있다.

이 문제처럼 정점끼리 서로 의존성이 존재하는 경우 위상정렬을 통해 올바른 순서를 찾을 수 있다.

이전까지는 DFS를 수행한 결과를 역순으로 출력하여 위상정렬을 수행하는 방법만 알고 있었는데,

이 문제를 통해 들어오는 간선의 개수(in degree)를 이용하여 위상정렬을 수행하는 방법을 새롭게 알게 되었다.

ps// 아래 블로그를 참고하여 풀었는데, 위상정렬에 대한 설명이 잘 되어있는 것 같다.

jason9319.tistory.com/93

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

vector<int> adj[32001];
int indegree[32001];

vector<int> topologicalSort(int N) {
	priority_queue<int> pq;
	for (int i = 1; i <= N; i++)
		if (indegree[i] == 0)
			pq.push(-i);
	
	vector<int> order;
	while (!pq.empty()) {
		int here = -pq.top();
		pq.pop();

		order.push_back(here);
		
		for (auto x : adj[here]) {
			indegree[x]--;
			if (indegree[x] == 0)
				pq.push(-x);
		}
	}
	return order;
}

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

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

	vector<int> result = topologicalSort(N);

	for (auto x : result)
		cout << x << ' ';

	return 0;
}

[문제 링크]

백트래킹과 BFS를 활용하여 풀 수 있는 문제였다.

입력으로 주어지는 바이러스들과 그 바이러스를 M개 활성화 시키는 모든 경우의 수를 백트레킹을 통해 완전탐색 하고, 모든 경우에 대해 바이러스를 확산시키는 BFS를 수행하여 가장 빠르게 확산되는 시간을 구해주면 원하는 결과를 얻을 수 있다.

시간이 0.25초로 제한되어 있기 때문에 2차원배열 전체를 순회하며 활성화 된 바이러스가 있는 위치를 찾아 확산시키는 방식으로 BFS를 구현하게 된다면 최악의 경우  (50^2) * (10개중 5개를 뽑는 조합의 수 252) * 50 =  31,500,000번 연산을 수행해야 하므로 제한 시간을 초과하게 된다. 따라서 배열 전체를 순회하는 방식이 아닌, 활성화 된 바이러스의 위치를 따로 저장하여 바이러스가 존재하는 좌표에 바로 접근할 수 있도록 구현하였다.

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

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N, M, cnt = 0, blank = 0;
int leastTime = INF;
int board[50][50];
Pos virus[10];

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(list<Pos> actVirus) {
	bool visited[50][50] = { false };
	for (auto x : actVirus)
		visited[x.y][x.x] = true;

	int change = 0;

	queue <int> q;
	q.push(0);

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

		if (change == blank) return time;
//		bool isChange = false;

		int listSize = actVirus.size();
		for (int i = 0; i < listSize; i++) {
			Pos here = actVirus.front();
			actVirus.pop_front();

			for (int j = 0; j < 4; j++) {
				int nearY = here.y + dy[j];
				int nearX = here.x + dx[j];
				if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < N && !visited[nearY][nearX])
					if (board[nearY][nearX] == 2 || board[nearY][nearX] == 0) {
						visited[nearY][nearX] = true;
//						isChange = true;
						actVirus.push_back({ nearY, nearX });
						if (board[nearY][nearX] == 0)
							change++;
					}
			}
		}
//		if (isChange) q.push(time + 1);
		if (!actVirus.empty()) q.push(time + 1);
	}

	return INF;
}

void backtracking(int start, list<Pos>& actVirus) {
	int select = actVirus.size();
	if (select == M) {
		leastTime = min(leastTime, bfs(actVirus));
		return;
	}

	for (int i = start; i < cnt; i++) {
		Pos pos = virus[i];
		actVirus.push_back({ pos.y, pos.x });
		backtracking(i + 1, actVirus);
		actVirus.pop_back();
	}
}

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) {
				virus[cnt].y = i;
				virus[cnt].x = j;
				cnt++;
			}
			else if (board[i][j] == 0)
				blank++;
		}

	list<Pos> actVirus;
	backtracking(0, actVirus);

	if (leastTime == INF)
		cout << -1 << endl;
	else
		cout << leastTime << endl;

	return 0;
}

[문제 링크]

문제를 풀기에 앞서 땅을 표현하는 Land 클래스와 로봇을 표현하는 Robot 클래스를 설계하였다.

로봇은 땅에 양분을 공급하는 역할을 수행한다. 따라서 Robot 클래스의 supplyNutrients() 메서드에서 Land 객체의 레퍼런스 타입을 매개변수로 받아 Land 클래스의 increaseNutrients() 메서드를 호출하여 땅에 양분을 공급하도록 설계하였다. 

Robot 클래스의 메서드에서 Land 클래스를 매개변수로 받는 형태를 이루고 있기 때문에 이 둘은 서로 연관 관계임을 알 수 있다. 따라서 연관 관계를 뜻하는 점선 화살표로 두 클래스를 연결하였다.

알고리즘은 다음과 같다.

1. N, M, K를 입력 받는다. 그다음 Land Size 값을 N으로 초기화한 Land 객체와 Robot 객체를 생성한다.

2. H2D2가 땅에 공급하는 양분을 배열로 입력 받아 설정한다.

3. 문제에서 요구하는 대로 봄, 여름, 가을, 겨울에 나타나는 일들을 그대로 구현한다.

4. 봄->여름->가을->겨울 순으로 함수를 호출한다. 그리고 이를 K번 반복한다.

5. K번 반복한 후 땅에 심어진 나무의 개수를 출력한다.

// 봄에 나무가 양분을 흡수하는 과정에서 나이가 어린 나무부터 양분을 먹도록 구현하기 위해 우선순위큐를 사용할 경우 나무를 심을 때마다 매번 정렬을 수행하게 되므로 시간복잡도가 커지게 된다.

따라서 나무를 vector에 담은 다음 나무가 양분을 흡수하는 작업이 실행되기 전에 정렬이 이루어지도록 구현하는 것이 효율적이다.

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

class Land {
private:
	int landSize;
	int nutrients[11][11];
	vector<int> livingTree[11][11];
	queue<int> deadTree[11][11];
public:
	Land(int N) : landSize(N) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				nutrients[y][x] = 5;
			}
		}
	}

	// 현재 심어진 나무의 개수를 반환한다.
	int getTreeCount() {
		int treeCnt = 0;
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				treeCnt += livingTree[y][x].size();
			}
		}

		return treeCnt;
	}

	// 나무를 심는다
	void plantTree(int y, int x, int treeAge) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize) {
			livingTree[y][x].push_back(treeAge);
		}
		else
			return;
	}

	// 나무가 땅의 양분을 흡수한다.
	void nourishTheTree() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				queue<int> growingTree;

				sort(livingTree[y][x].begin(), livingTree[y][x].end(), greater<int>());

				while (!livingTree[y][x].empty()) {
					int treeAge = livingTree[y][x].back();
					livingTree[y][x].pop_back();

					if (nutrients[y][x] >= treeAge) {
						nutrients[y][x] -= treeAge;
						growingTree.push(treeAge + 1);
					}
					else {
						deadTree[y][x].push(treeAge);
					}
				}

				while (!growingTree.empty()) {
					int treeAge = growingTree.front();
					growingTree.pop();

					livingTree[y][x].push_back(treeAge);
				}
			}
		}
	}

	// 땅의 양분을 증가시킨다.
	void increaseNutrients(int y, int x, int val) {
		if (y >= 1 && y <= landSize && x >= 1 && x <= landSize)
			nutrients[y][x] += val;
		else
			return;
	}

	// 죽은 나무가 땅의 양분으로 변환된다.
	void convertToNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				while (!deadTree[y][x].empty()) {
					int newNutrients = deadTree[y][x].front() / 2;
					deadTree[y][x].pop();

					increaseNutrients(y, x, newNutrients);
				}
			}
		}
	}

	// 나이가 5의 배수인 나무가 번식한다.
	void treeMultiply() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				int treeSize = livingTree[y][x].size();
				for (int i = 0; i < treeSize; i++) {
					int treeAge = livingTree[y][x][i];
					if (treeAge % 5 == 0) {
						for (int i = -1; i < 2; i++) {
							for (int j = -1; j < 2; j++) {
								if (i == 0 && j == 0) continue;
								plantTree(y + i, x + j, 1);
							}
						}
					}
				}
			}
		}
	}
};

class Robot {
private:
	int landSize;
	int nutrients[11][11];
public:
	Robot(int N) : landSize(N) { }

	// 공급하는 양분의 양을 설정한다.
	void setNutrients() {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				cin >> nutrients[y][x];
			}
		}
	}

	// 땅에 양분을 공급한다.
	void supplyNutrients(Land& land) {
		for (int y = 1; y <= landSize; y++) {
			for (int x = 1; x <= landSize; x++) {
				land.increaseNutrients(y, x, nutrients[y][x]);
			}
		}
	}
};

void springAction(Land& land) {
	land.nourishTheTree();
}

void summerAction(Land& land) {
	land.convertToNutrients();
}

void fallAction(Land& land) {
	land.treeMultiply();
}

void winterAction(Land& land, Robot& robot) {
	robot.supplyNutrients(land);
}

void printYearsHavePassed(Land& land, Robot& robot, int K) {
	for (int i = 0; i < K; i++) {
		springAction(land);
		summerAction(land);
		fallAction(land);
		winterAction(land, robot);
	}

	cout << land.getTreeCount() << endl;
}

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

	Land land(N);
	Robot S2D2(N);

	S2D2.setNutrients();

	for (int i = 0; i < M; i++) {
		int x, y, z;
		cin >> y >> x >> z;
		land.plantTree(y, x, z);
	}

	printYearsHavePassed(land, S2D2, K);

	return 0;
}

[문제 링크]

문제를 풀기에 앞서 문제에서 주어진 지도와 경사로, 그리고 지도와 경사로를 이용해 지나갈 수 있는 길인지 파악하는 역할을 하는 사람을 클래스 다이어그램으로 표현하였다.

사람은 지형이 그려진 지도와 설치할 수 있는 경사로를 "가지고" 있다고 볼 수 있기 때문에

"사람은 지도와 경사로를 포함한다." 라는 has-A 관계가 성립된다.

따라서 필자는 클래스 다이어그램을 다음과 같이 작성하였다.

알고리즘은 다음과 같다.

1. 입력받은 정보를 통해 지도와 경사로 객체를 생성한다.

2. 지도와 경사로 객체를 속성으로 가지는 사람 객체를 생성한다.

3. 한쪽 끝에서 반대쪽 끝으로 가는 길을 찾는 것이기 때문에 1열의 모든 좌표에서 아래방향으로 탐색하고, 1행의 모든 좌표에서 오른쪽 방향으로 탐색하여 가능한 길의 갯수를 샌다.

 3-1. IF 현재 지형의 높이가 이전 지형의 높이와 같다면 경사로를 놓을 필요 없이 다음 지형으로 넘어간다.

ELSE IF 현재 지형의 높이가 더 낮다면 현재 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

ELSE IF 현재 지형의 높이가 더 높다면 경사로의 길이 L만큼 뒤에 위치한 지형을 시작으로 경사로를 놓을 수 있는지 검사한다. 경사로를 놓을 수 없다면 탐색을 종료한다.

추가로, 이미 경사로를 설치한 지형에 중복으로 설치할 수 없으므로 경사로 설치 여부를 저장하는 배열을 통해 중복 설치를 방지하였다.

#include <iostream>
using namespace std;

class Map {
private:
	int N;
	int arr[101][101];

public:
	Map() : N(0) {}
	Map(int _N) : N(_N) {}

	void setTopography() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> arr[i][j];
	}

	int getMapSize() {
		return N;
	}

	int getTopographyHeight(int y, int x) {
		if (y < 0 || y >= N || x < 0 || x >= N)
			return 0;

		return arr[y][x];
	}
};

class Runway {
private:
	int L;

public:
	Runway() : L(0) {}
	Runway(int _L) : L(_L) {}

	int getRunwayLength() {
		return L;
	}
};

enum {
	RIGHT, DOWN
};

class Person {
private:
	Map map;
	Runway runway;

	int readMap(int y, int x) {
		return map.getTopographyHeight(y, x);
	}

	bool isLayRunway(int y, int x, int height, bool layRunway[][101], int state) {
		int L = runway.getRunwayLength();

		switch (state) {
		case RIGHT:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y, x + i);
				if (layRunway[y][x + i] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y][x + i] = true;
			}
			return true;

		case DOWN:
			for (int i = 0; i < L; i++) {
				int adjHeight = readMap(y + i, x);
				if (layRunway[y + i][x] || adjHeight == 0 || adjHeight != height - 1)
					return false;
				layRunway[y + i][x] = true;
			}
			return true;
		}

		return false;
	}
public:
	Person(Map& _map, Runway& _runway) {
		this->map = _map;
		this->runway = _runway;
	}

	bool isCheckPath(int y, int x, int state) {
		int N = map.getMapSize();
		int L = runway.getRunwayLength();

		if (y >= N || x >= N) return false;

		bool layRunway[101][101] = { false };
		int lastHeight = readMap(y, x);

		switch (state) {
		case RIGHT:
			while (++x < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, RIGHT))
						return false;
					x += L - 1;
				}
				else {
					x -= L;
					if (!isLayRunway(y, x, height, layRunway, RIGHT))
						return false;
					x += L;
				}

				lastHeight = height;
			}
			return true;

		case DOWN:
			while (++y < N) {
				int height = readMap(y, x);
				if (lastHeight == height)
					continue;
				else if (lastHeight > height) {
					if (!isLayRunway(y, x, lastHeight, layRunway, DOWN))
						return false;
					y += L - 1;
				}
				else {
					y -= L;
					if (!isLayRunway(y, x, height, layRunway, DOWN))
						return false;
					y += L;
				}

				lastHeight = height;
			}
			return true;
		}

		return false;
	}
};

void printAllPath(Map& map, Runway& runway) {
	Person person(map, runway);
	int pathCnt = 0;

	for (int y = 0; y < 100; y++)
		if (person.isCheckPath(y, 0, RIGHT)) {
			pathCnt++;
		}

	for (int x = 0; x < 100; x++)
		if (person.isCheckPath(0, x, DOWN)) {
			pathCnt++;
		}

	cout << pathCnt << endl;
}

int main(void) {
	int N, L;
	cin >> N >> L;

	Map map(N);
	Runway runway(L);

	map.setTopography();
	printAllPath(map, runway);

	return 0;
}

[문제 링크]

문제에서 치즈가 놓인 판을 객체로 표현하기 위해 클래스의 속성과 메서드를 다음과 같이 정의하였다.

알고리즘은 다음과 같다.

1. 치즈를 놓을 판의 객체를 생성한다.

2. 가로 길이와 세로 길이를 입력 받은 다음, 치즈가 놓여있는 상태를 입력받아 배열에 담는다.

3. 판 위에 놓인 치즈가 모두 녹을 때 까지 (0, 0)을 시작점으로 하는 BFS를 수행하여 치즈를 녹인다.

4. 치즈가 모두 녹았다면 경과한 시간과 1시간 전에 남아있던 치즈의 개수를 출력한다.

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

int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

struct Pos {
	int y;
	int x;
};

class Plate {
private:
	int col, row;
	int cheezeCnt;
	int arr[101][101];
public:
	Plate() : cheezeCnt(0), col(0), row(0) {
		memset(arr, sizeof(arr), 0);
	}

	void setPlate() {
		cin >> col >> row;

		for (int i = 0; i < col; i++)
			for (int j = 0; j < row; j++) {
				cin >> arr[i][j];

				if (arr[i][j] == 1) cheezeCnt++;
			}
	}

	// bfs
	void meltCheeze() {
		bool visited[101][101] = { false };
		int tempArr[101][101];
		memcpy(tempArr, arr, sizeof(tempArr));

		queue<Pos> q;
		q.push({ 0,0 });
		visited[0][0] = true;

		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 >= col || there.x < 0 || there.x >= row)
					continue;

				if (tempArr[there.y][there.x] == 0 && !visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					q.push(there);
				}
				else if (tempArr[there.y][there.x] == 1 && !visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					arr[there.y][there.x] = 0;
					cheezeCnt--;
				}
			}
		}
	}

	int getCheezeCount() {
		return cheezeCnt;
	}
};

void printAllMeltTime(Plate& plate) {
	int time = 0;
	int lastCheezeCnt = plate.getCheezeCount();

	while (1) {
		plate.meltCheeze();
		time++;

		if (plate.getCheezeCount() != 0)
			lastCheezeCnt = plate.getCheezeCount();
		else
			break;
	}

	cout << time << '\n' << lastCheezeCnt << endl;
}

int main(void) {
	Plate plate;
	plate.setPlate();
	printAllMeltTime(plate);

	return 0;
}

#include <iostream>
using namespace std;

// 원소 교환
void swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

// 선택정렬 
// time complexity : O(n^2)
void selectionSort(int arr[], int len) {
	for (int i = 0; i < len; i++) {
		int idx = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[idx] >= arr[j])
				idx = j;
		}

		swap(arr, i, idx);
	}
}

// 삽입정렬 
// 정렬 되어있는 경우 time complexity : O(n)
// 정렬 되어있지 않는 경우 time complexity : O(n^2);
void insertionSort(int arr[], int len) {
	for (int i = 1; i < len; i++) {
		int val = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (val < arr[j]) {
				arr[j + 1] = arr[j];
				arr[j] = val;
			}
			else {
				break;
			}
		}
	}
}

// 버블정렬
// time complexity : O(n^2)
void bubbleSort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++) {
		for (int j = 0; j < len - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
			}
		}
	}
}

// 퀵정렬
// 평균, 최고 time complexity : O(n log n)
// 최악 time complexity : O(n^2) <--- 최적화 전
// 퀵정렬 최적화 -> left, mid, right 값 중에서 중간값을 pivot으로 선택하도록 구현
// 선택한 pivot과 left 값을 서로 바꾼다
int getMidIndex(int arr[], int left, int right) {
	int mid = (left + right) / 2;
	int idx[3] = { left, mid, right };

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	if (arr[idx[1]] > arr[idx[2]]) {
		swap(idx, 1, 2);
	}

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	return idx[1];
}

void quickSort(int arr[], int left, int right) {
	if (left >= right) return;

	int pIdx = getMidIndex(arr, left, right);
	swap(arr, left, pIdx);

	int pivot = left;
	int low = left + 1;
	int high = right;

	while (1) {
		while (low <= right && arr[low] <= arr[pivot])
			low++;
		while (high > left && arr[high] >= arr[pivot])
			high--;

		if (low > high) // low, high 가 서로 교차했다면
			break;

		int temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
	}

	int temp = arr[pivot];
	arr[pivot] = arr[high];
	arr[high] = temp;

	quickSort(arr, left, high - 1);
	quickSort(arr, high + 1, right);
}

// 병합정렬
// time complexity : O(n log n)
// 정렬한 배열을 임시로 저장할 임시 메모리가 필요한 단점이 있다
// 정렬의 대상이 배열이 아닌 리스트일 경우 임시 메모리 필요 없어서 좋은 성능 발휘
void merge(int arr[], int left, int mid, int right) {
	int idx1 = left;
	int idx2 = mid + 1;

	int* temp = new int[right + 1];
	int idx = left;

	while (idx1 <= mid && idx2 <= right) {
		if (arr[idx1] < arr[idx2]) // idx1이 가리키는 값이 idx2가 가리키는 값보다 작다면
			temp[idx++] = arr[idx1++];
		else
			temp[idx++] = arr[idx2++];
	}

	if (idx1 > mid)
		while (idx2 <= right)
			temp[idx++] = arr[idx2++];
	else
		while (idx1 <= mid)
			temp[idx++] = arr[idx1++];

	for (int i = left; i <= right; i++)
		arr[i] = temp[i];

	delete[] temp;
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);

		merge(arr, left, mid, right);
	}
}


int main(void) {
	int arr[10] = { 3,4,5,6,1,10,2,7,8,9 };

	//	selectionSort(arr, 10);
	//	insertionSort(arr, 10);
	//	bubbleSort(arr, 10);
	//	quickSort(arr, 0, 9);
	mergeSort(arr, 0, 9);

	for (auto x : arr)
		cout << x << ' ';
}

[문제 링크]

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

먼저 크기가 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

[문제 링크]

문제를 보고 생각난 알고리즘은 플로이드-와샬 알고리즘이었다. 하지만 N이 최대 800이므로 O(N^3)이면 약 5억이 넘게 되어 시간초과가 날 것이라 생각하고 다익스트라 알고리즘으로 구현하였다.

정점 v1과 v2를 반드시 지나야 하기 때문에 1부터 N까지 갈 수 있는 방법은 아래 두가지 경로만 가능하다.

경로 1) dist[1][v1] -> dist[v1][v2] -> dist[v2][N] 

경로 2) dist[1][v2] -> dist[v2][v1] -> dist[v1][N]

dist[v1][v2] 와 dist[v2][v1] 의 최단경로는 서로 같으므로, 3개의 정점 1, v1, N 을 출발점으로 하는 다익스트라 알고리즘을 수행하여 최단경로를 계산해주면 된다.

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

// INF를 987654321로 할 경우
// 62~63 라인에서 int의 최대 범위 넘어갈 수 있다.
const int INF = 700000000;
int N, E;
vector<vector<pair<int, int>>> adj(801);
vector<vector<int>> allDist(801, vector<int>(801, INF));

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 });
			}
		}
	}

	allDist[start] = dist;
}

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

	cin >> N >> E;

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

	int v1, v2;
	cin >> v1 >> v2;

	dijkstra(1);
	dijkstra(v1);
	dijkstra(N);

	int path1 = allDist[1][v1] + allDist[v1][v2] + allDist[v2][N];
	int path2 = allDist[1][v2] + allDist[v1][v2] + allDist[v1][N];

	int result = min(path1, path2);

	if (result >= INF)
		cout << -1 << endl;
	else
		cout << result << endl;

	return 0;
}

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