언제나 처음처럼

[문제 링크]

트라이 자료구조를 활용하는 문제였다.

우선 전화번호 목록을 트라이에 담으면서 전화번호의 끝자리인 노드를 체크하였다.

그다음, 완성된 트라이에서 전화번호를 검색하여 끝자리에 도달하기 전에 다른 전화번호의 끝자리인 노드에 방문하게 되는지 여부를 판단하여 입력받은 전화번호 목록이 일관성 있는 목록인지 아닌지를 알 수 있다.

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

const int NUMBER = 10;

class TrieNode {
	TrieNode* children[NUMBER];
	bool terminal;

public:
	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}
	~TrieNode() {
		for (int i = 0; i < NUMBER; i++)
			if (children[i] != 0) delete children[i];
	}

	void insert(string& key, int here) {
		if (here == key.size()) 
			terminal = true;
		else {
			int next = key[here] - '0';
			if (children[next] == NULL)
				children[next] = new TrieNode();

			children[next]->insert(key, here + 1);
		}
	}

	bool find(string& key, int here) {
		if (here == key.size()) return true;
		
		if (this->terminal)
			return false;

		int next = key[here] - '0';
		return children[next]->find(key, here + 1);
	}
};

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

	int t;
	cin >> t;
	
	while (t--) {
		int n;
		cin >> n;

		vector<string> numberList(10001);
		TrieNode* trie = new TrieNode();

		for (int i = 0; i < n; i++) {
			string num;
			cin >> num;
			numberList[i] = num;
			trie->insert(num, 0);
		}

		bool flag = true;
		for (int i = 0; i < n; i++) {
			if (!trie->find(numberList[i], 0)) {
				cout << "NO" << '\n';
				flag = false;
				break;
			}
		}
		if (flag)
			cout << "YES" << '\n';

		delete trie;
	}
}

[문제 링크]

재밌으면서도 골치아팠던 그래프 & 시뮬레이션 문제였다.

우선 궁수를 3명 배치하는 조합의 경우 3중 for문을 이용하여 간단하게 구현할 수 있다.

그 다음, 궁수가 공격할 대상을 정하는 것을 구현해야 하는데 조건은 다음과 같다.

1. 궁수는 동시에 공격한다. --> 같은 적을 여러명의 궁수가 공격하게 될 수 있다.

2. 사거리 내 적이 여러명 있는 경우 가장 가까이 있는 적을 공격한다.

3. 같은 사거리에 있는 적의 경우 가장 왼쪽에 있는 적을 공격한다.

여러명의 궁수가 같은 적을 공격하는 경우 킬포인트가 중복으로 누적되는 것을 방지하기 위해 이미 죽은 적은 '2'로 마킹하여 공격은 하되, 킬포인트는 올라가지 않도록 구현하였다.

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

int N, M, D;
int board[15][15];

class Archer {
private:
	int y;
	int x;
	int distance;
	int kill;
public:
	Archer(int _x) : y(N), distance(D), kill(0) {
		x = _x;
	}

	void searchEnemy() {
		for (int d = 1; d <= distance; d++) {
			int i = 1;
			while (i <= d) {
				int yPos = y - i;
				int xPos = x - d + i;

				if (yPos >= 0 && xPos >= 0) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i++;
			}

			i = d - 1;

			while (i >= 1) {
				int yPos = y - i;
				int xPos = x + d - i;

				if (yPos >= 0 && xPos < M) {
					int& enemy = board[yPos][xPos];
					if (enemy != 0) {
						attack(enemy);
						return;
					}
				}

				i--;
			}
		}
	}

	void attack(int& enemy) {
		if (enemy == 1) {
			enemy = 2;
			kill++;
		}
	}

	int getKillCount() {
		return kill;
	}
};

void moveEnemy() {
	int temp[15][15];
	memcpy(temp, board, sizeof(temp));

	for (int y = N-1; y >= 0; y--) {
		for (int x = 0; x < M; x++) {
			int state = temp[y][x];
			if (state != 0) {
				if (state == 1) {
					int nextY = y + 1;
					if (nextY < N)
						board[nextY][x] = 1;
				}
				board[y][x] = 0;
			}
		}
	}
}

bool isEndGame() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (board[i][j] == 1)
				return false;

	return true;
}

int maximumKillCount() {
	int result = 0;

	for (int i = 0; i < M; i++) {
		for (int j = i + 1; j < M; j++) {
			for (int k = j + 1; k < M; k++) {
				int killCount = 0;

				Archer* archer1 = new Archer(i);
				Archer* archer2 = new Archer(j);
				Archer* archer3 = new Archer(k);

				int backup[15][15];
				memcpy(backup, board, sizeof(backup));

				while (!isEndGame()) {
					archer1->searchEnemy();
					archer2->searchEnemy();
					archer3->searchEnemy();

					moveEnemy();
				}

				killCount += archer1->getKillCount();
				killCount += archer2->getKillCount();
				killCount += archer3->getKillCount();

				result = max(result, killCount);

				memcpy(board, backup, sizeof(board));

				delete archer1;
				delete archer2;
				delete archer3;
			}
		}
	}

	return result;
}

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

	cout << maximumKillCount() << endl;

	return 0;
}

[문제 링크]

간단한 다이나믹 프로그래밍 문제였다.

입력받은 물품 목록 배열에서, 현재 보고있는 물품의 무게가 준서가 버틸 수 있는 무게보다 무겁지 않을 경우 해당 물품을 가방에 담았을 때 나올 수 있는 최대 가치값과 담지 않았을 때 나올 수 있는 최대 가치값을 비교하여 더 큰 가치값을 선택하도록 구현하면 된다.

따라서 점화식은 다음과 같다.

maxValue = max(dp(here+1, weight + itemWeight) + itemValue , dp(here+1, weight))

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

int N, K, V, W;
int memo[101][100001];

//first : W, second : V
vector<pair<int, int>> item;

int dp(int here, int weight) {
	// 기저사례 : N개의 물건을 모두 탐색했다면 재귀를 종료한다.
	if (here == N) return 0;

	int& ret = memo[here][weight];
	if (ret != -1) return ret;

	if (weight + item[here].first <= K)
		return ret = max(dp(here + 1, weight + item[here].first) + item[here].second, dp(here + 1, weight));
	else
		return ret = dp(here + 1, weight);
}

int main(void) {
	memset(memo, -1, sizeof(memo));

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> W >> V;
		item.push_back({ W,V });
	}

	cout << dp(0, 0) << endl;
}

https://www.acmicpc.net/problem/1600

원숭이의 좌표와 말처럼 이동할 수 있는 횟수가 몇번 남았는지에 대한 정보, 이동한 횟수를 queue에 담아서 bfs를 수행하면 원하는 결과를 얻을 수 있다.

한가지 유의할 점은 말처럼 이동할 경우 장애물을 뛰어넘을 수 있기 때문에 이미 방문한 좌표라도 말처럼 이동할 수 있는 횟수가 남아있느냐 남아있지 않느냐에 따라 결과값이 달라지게 된다.

따라서, 중복탐색을 피하기 위한 visited 배열을 좌표 정보만 담은 2차원 배열이 아닌, 말처럼 이동한 횟수까지 포함하는 3차원 배열로 선언해야 한다.

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

int K, H, W;
int board[200][200];
bool visited[200][200][31];

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

struct Pos {
	int y;
	int x;
};

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

	while (!q.empty()) {
		int hereY = q.front().first.first.y;
		int hereX = q.front().first.first.x;
		int horse = q.front().first.second;
		int move = q.front().second;

		q.pop();

		if (hereY == H - 1 && hereX == W - 1)
			return move;

		for (int i = 0; i < 12; i++) {
			if (horse <= 0 && i < 8) continue;
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];
			if (nextY >= 0 && nextY < H && nextX >= 0 && nextX < W) {
				if (i < 8) {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse - 1]) {
						q.push({ {{nextY, nextX}, horse - 1 }, move + 1 });
						visited[nextY][nextX][horse - 1] = true;
					}
				}
				else {
					if (board[nextY][nextX] == 0 && !visited[nextY][nextX][horse]) {
						q.push({ {{nextY, nextX}, horse}, move + 1 });
						visited[nextY][nextX][horse] = true;
					}
				}
			}
		}
	}

	return -1;
}
int main(void) {
	cin >> K >> W >> H;

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

	cout << bfs() << endl;

	return 0;
}

[문제 링크]

간단한 bfs 문제였다.

수빈이가 +1, -1로 이동하는 경우와, *2로 이동하는 경우에 대해서 bfs를 돌려서 동생을 찾는 가장 빠른 방법을 찾으면 된다.

수빈이가 이동하는 경로를 저장하기 위해 queue에 현재 위치와 그동안 이동했던 경로를 담은 queue를 pair 자료구조에 담았다.

한가지 함정이 있다면, 수빈이가 동생보다 앞에 있을 경우, +1과 *2로 이동하게 되면 반드시 더 멀어지게 되기 때문에 -1로만 이동하게 된다.

극단적인 예로 만약 수빈이가 100000에 위치해 있고, 동생이 0에 위치해 있는 경우 수빈이의 이동경로는 100000 99999 99998 .... 0 이 된다. 이 경로를 queue에 전부 담게 되면 시간복잡도 및 공간복잡도가 매우 커지게 된다.

따라서 시작지점이 수빈이가 동생보다 앞일 경우, bfs를 수행하지 않고 -1로 이동하는 경로를 출력하도록 구현하였다.

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

bool visited[100001];

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

	while (!q.empty()) {
		int here = q.front().first;
		queue<int> route = q.front().second;
		q.pop();

		if (here == K) return route;

		for (int i = 0; i < 3; i++) {
			int next;
			if (i == 0) next = here + 1;
			else if (i == 1) next = here - 1;
			else next = here * 2;

			if (next >= 0 && next <= 100000 && !visited[next]) {
				queue<int> temp = route;
				temp.push(next);
				q.push({ next, temp });
				visited[next] = true;
			}
		}
	}

	return queue<int>();
}

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

	if (N >= K) {
		cout << N - K << endl;
		while (N >= K)
			cout << N-- << ' ';
	}
	else {
		queue<int> result = bfs(N, K);

		cout << result.size() - 1 << endl;
		while (!result.empty()) {
			cout << result.front() << ' ';
			result.pop();
		}
	}

	return 0;
}

[문제 링크]

간단해보이지만 함정이 하나 있는 문제였다.

치즈가 공기와 접촉하는지 확인하기 위해 치즈 기준 동서남북 방향에 0이 있는지 체크하고 0이 두군데 이상 있다면 공기와 접촉하고 있다고 단정 지을 수 있는데, 치즈로 둘러 쌓인 내부의 0은 공기가 통하지 않기 때문에 이를 제외시켜줘야 한다.

따라서, 치즈를 녹이기 전에 {0, 0} 좌표를 시작으로 BFS를 수행하여 실제로 공기가 통하는 좌표를 먼저 마킹했다.

그 다음 전체 판을 탐색하여 공기와 접해있는 면이 2개 이상인 치즈를 녹이는 방식으로 구현하였다.

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

int N, M, cheezeCnt = 0;
int board[101][101];
bool isAir[101][101];

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

void markingAir() {
	queue<pair<int, int>> q;
	memset(isAir, false, sizeof(isAir));

	q.push({ 0,0 });
	isAir[0][0] = true;

	while (!q.empty()) {
		int hereY = q.front().first;
		int hereX = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nearY = hereY + dy[i];
			int nearX = hereX + dx[i];
			if (nearY >= 0 && nearY < N && nearX >= 0 && nearX < M) {
				if (board[nearY][nearX] == 0 && !isAir[nearY][nearX]) {
					q.push({ nearY, nearX });
					isAir[nearY][nearX] = true;
				}
			}
		}
	}
}

void meltCheeze() {
	int temp[101][101];

	memcpy(temp, board, sizeof(board));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (temp[i][j] == 1) {
				int air = 0;

				for (int k = 0; k < 4; k++) {
					int nearY = i + dy[k];
					int nearX = j + dx[k];
					if (isAir[nearY][nearX])
						air++;
				}

				if (air >= 2) {
					board[i][j] = 0;
					cheezeCnt--;
				}
			}
		}
	}
}

int getAllMeltCheezeTime() {
	int time = 0;

	while (cheezeCnt) {
		markingAir();
		meltCheeze();
		time++;
	}

	return time;
}

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

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			int n;
			cin >> n;
			board[i][j] = n;
			if (board[i][j] == 1)
				cheezeCnt++;
		}

	cout << getAllMeltCheezeTime() << endl;

	return 0;
}

[문제 링크]

이진트리의 전위순회, 중위순회, 후위순회를 구현하는 문제였다.

이진트리에서 노드는 자식노드를 가지고 있지 않더라도 공집합 노드를 가지고있는 하나의 이진트리라고 볼 수 있기 때문에 별도의 노드 구조체를 정의하지 않고, BTree 클래스를 정의하여 구현하였다.

#include <iostream>
using namespace std;

class BTree {
	char data;
	BTree* left;
	BTree* right;
public:
	BTree(char c) : data(c), left(NULL), right(NULL) { }
	
	void makeLeftSubTree(BTree* sub) {
		this->left = sub;
	}

	void makeRightSubTree(BTree* sub) {
		this->right = sub;
	}

	void printData() {
		cout << data;
	}

	BTree* findNode(char c) {
		BTree* node = NULL;

		if (this->data == c)
			node = this;
		if (left != NULL && node == NULL) node = left->findNode(c);
		if (right != NULL && node == NULL) node = right->findNode(c);

		return node;
	}

	void preorder() {
		printData();
		if(left != NULL)  left->preorder();
		if(right != NULL) right->preorder();
	}

	void inorder() {
		if (left != NULL)  left->inorder();
		printData();
		if (right != NULL) right->inorder();
	}

	void postorder() {
		if (left != NULL)  left->postorder();
		if (right != NULL) right->postorder();
		printData();
	}

	void deleteTree() {
		if (left != NULL)
			left->deleteTree();
		if (right != NULL)
			right->deleteTree();

		delete this;
	}
};

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

	BTree* tree = new BTree('A');
	for (int i = 0; i < N; i++) {
		char parent, left, right;
		cin >> parent >> left >> right;

		if (left != '.') {
			BTree* lNode = new BTree(left);
			tree->findNode(parent)->makeLeftSubTree(lNode);
		}
		if (right != '.') {
			BTree* rNode = new BTree(right);
			tree->findNode(parent)->makeRightSubTree(rNode);
		}
	}

	tree->preorder();
	cout << '\n';
	tree->inorder();
	cout << '\n';
	tree->postorder();

	tree->deleteTree();

	return 0;
}

[문제 링크]

왠지 영어로 된 알고리즘 문제를 풀어봐야 할 것 같아서 풀게되었다.

문제는 간단했다. 한 블록을 뒤집으면 상하좌우에 존재하는 블록들까지 동시에 뒤집어지는데, 모든 블록을 블랙 또는 화이트가 되도록 만들기 위해 뒤집는 최소한의 횟수를 구하는 문제였다.

최소한의 횟수를 구하기 위해 bfs를 구현하면 간단히 풀 수 있는 문제인데, 한가지 문제가 있다면 이전에 등장했던 보드판의 상태를 중복탐색 하는 것을 막기 위해 방문체크를 해줘야 하는데, 블록의 형태를 어떻게 표현할 것인지가 문제였다.

보드판은 항상 4x4 이므로 보드판에 존재하는 블록의 개수 또한 항상 16개라는 것을 알 수 있다.

따라서, 비트마스크 기법을 활용하면 보드판의 상태를 integer 타입의 정수형 데이터로 표현하는 것이 가능하다.

보드판의 좌표 (y,x)를 (4*y)+x 공식에 대입하여 자릿수를 구한 다음, OR 연산을 통해 해당 자릿수의 값을 블랙일 경우 1, 화이트일 경우 0으로 세팅하고, 공을 뒤집는 작업은 XOR 연산을 통해 값을 반전시켜줌으로써 간단하게 보드판을 관리할 수 있다.

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

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

int ptod(int y, int x) {
	return (y * 4) + x;
}

int bfs(int start) {
	int allBlack = (1 << 16) - 1;
	int allWhite = 0;
	bool visited[(1 << 16)] = { false };

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

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

		if (here == allBlack || here == allWhite)
			return round;

		for(int i=0; i<4; i++)
			for (int j = 0; j < 4; j++) {
				int there = here;
				there ^= (1 << (ptod(i, j)));

				for (int k = 0; k < 4; k++) {
					int nextY = i + dy[k];
					int nextX = j + dx[k];
					if (nextY >= 0 && nextY < 4 && nextX >= 0 && nextX < 4) {
						there ^= (1 << (ptod(nextY, nextX)));
					}
				}
				if (!visited[there]) {
					visited[there] = true;
					q.push({ there, round + 1 });
				}
			}
	}

	return -1;
}

int solution(vector<string>& input) {
	int inputNumber = 0;
	for(int i=0; i<4; i++)
		for (int j = 0; j < 4; j++) {
			int digit = ptod(i, j);
			if (input[i][j] == 'b')
				inputNumber |= (1 << digit);
		}

	return bfs(inputNumber);
}

int main(void) {
	vector<string> input;
	for (int i = 0; i < 4; i++) {
		string s;
		cin >> s;
		input.push_back(s);
	}

	int result = solution(input);
	if (result != -1)
		cout << result;
	else
		cout << "Impossible";

	return 0;
}