언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/229    

예전에 풀었던 토마토 문제와 동일한 문제였다.

차이점은 상자의 상태가 3차원 배열이라는 점이다.

따라서, 기존의 구현 코드에서 상자를 3차원 배열로 변경하고 Z 좌표가 바뀌는 경우를 추가해주었다.

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

struct boxPos {
	int z, y, x;
};

int M, N, H;
int box[101][101][101];
queue<boxPos> ripeTomatoPosQ;
int dz[6] = { 0,0,0,0,1,-1 };
int dy[6] = { 0,0,1,-1,0,0 };
int dx[6] = { 1,-1,0,0,0,0 };

int getDay(int unripeTomato) {
	int day = 0;

	while (unripeTomato > 0) {
		day++;

		int newRipeTomatoCnt = ripeTomatoPosQ.size();
		// 안익은 토마토가 남아있는 상태에서 새롭게 익은 토마토가 없다면 토마토를 모두 익히는건 불가능하다.
		if (newRipeTomatoCnt == 0)
			return -1;

		for (int i = 0; i < newRipeTomatoCnt; i++) {
			int hereZ = ripeTomatoPosQ.front().z;
			int hereY = ripeTomatoPosQ.front().y;
			int hereX = ripeTomatoPosQ.front().x;
			ripeTomatoPosQ.pop();

			// 주변의 토마토를 익힌다.
			for (int i = 0; i < 6; i++) {
				int nearZ = hereZ + dz[i];
				int nearY = hereY + dy[i];
				int nearX = hereX + dx[i];

				if (nearZ >= 0 && nearZ < H && nearY >= 0 && nearY < N && nearX >= 0 && nearX < M)
					if (box[nearZ][nearY][nearX] == 0) {
						// 안익은 토마토를 익은 토마토로 바꾸고 안익은 토마토의 갯수를 1 감소시킨다.
						box[nearZ][nearY][nearX] = 1;
						unripeTomato--;

						// 새롭게 익은 토마토의 좌표를 큐에 담는다.
						ripeTomatoPosQ.push({ nearZ, nearY, nearX });
					}
			}
		}
	}

	return day;
}

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

	cin >> M >> N >> H;

	int unripeTomato = 0;
	for (int z = 0; z < H; z++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				int state;
				cin >> state;
				box[z][y][x] = state;
				if (state == 0)
					unripeTomato++;
				else if (state == 1)
					ripeTomatoPosQ.push({ z,y,x });
			}
		}
	}

	cout << getDay(unripeTomato) << endl;

	return 0;
}

[문제 링크]

문자열과 관련된 구현 문제였다.

문자열의 길이가 최대 100,000이기 때문에 뒤집기 연산을 할 때 실제 문자열을 뒤집으면 시간 복잡도가 너무 커지게 된다.

따라서 뒤집기 연산을 할 때마다 isReversed 변수를 토글하여 현재 뒤집힌 상태인지 아닌지를  저장하고,

버리기 연산을 하게 될 경우 현재 뒤집히지 않은 상태라면 앞에서 숫자를 빼고, 뒤집힌 상태라면 뒤에서 숫자를 빼는 방식으로 구현하였다.

앞, 뒤에서 자유롭게 원소를 넣고 빼는 연산을 수행하기 위해 자료구조는 Deque를 사용하였다.

마지막으로 문자열을 출력하는 연산에서는

뒤집히지 않은 상태라면 Deque의 앞에서부터 하나씩 그대로 출력해주면 되며,

뒤집힌 상태일 경우 Deque의 뒤에서부터 하나씩 빼는데 그대로 출력하면 숫자가 뒤집혀서 출력되기 때문에 숫자를 임시로 저장하는 Stack 컨테이너에 옮겨 담아서 출력하였다.

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

void printAC(string acStr, string func) {
	deque<char> dq;
	for (auto x : acStr)
		dq.push_back(x);

	dq.pop_front();
	dq.pop_back();

	bool isReversed = false;

	for (auto x : func) {
		if (x == 'R')
			isReversed = !isReversed;
		else {
			if (dq.empty()) {
				cout << "error";
				return;
			}

			char hereChar;
			if (!isReversed) {
				hereChar = dq.front();
				dq.pop_front();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.front();
					dq.pop_front();
				}

			}
			else {
				hereChar = dq.back();
				dq.pop_back();

				while (!dq.empty() && hereChar != ',') {
					hereChar = dq.back();
					dq.pop_back();
				}

			}
		}
	}

	char hereChar;

	cout << '[';
	if (!isReversed) {
		while (!dq.empty()) {
			hereChar = dq.front();
			dq.pop_front();

			cout << hereChar;
		}
	}
	else {
		stack<char> tempStk;
		while (!dq.empty()) {
			hereChar = dq.back();
			dq.pop_back();

			if (hereChar != ',')
				tempStk.push(hereChar);
			else {
				while (!tempStk.empty()) {
					cout << tempStk.top();
					tempStk.pop();
				}
				cout << hereChar;
			}
		}
		while (!tempStk.empty()) {
			cout << tempStk.top();
			tempStk.pop();
		}
	}
	cout << ']';
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		string func;
		cin >> func;

		int n;
		cin >> n;

		string acStr;
		cin >> acStr;

		printAC(acStr, func);
		cout << '\n';
	}

	return 0;
}

[문제 링크]

N과 M의 최댓값이 500,000으로 매우 크기 때문에 일반적인 탐색으로는 제한 시간내에 정답을 구할 수 없다.

따라서 이분 탐색으로 원소를 찾도록 구현해야 한다.

c++ STL에 정의된 Set 컨테이너를 사용하면 쉽게 구현할 수 있다.

Set 컨테이너는 균형 이진 트리로 구현되어 있으므로 원소를 추가하면 자동으로 정렬되며, 원소를 로그 시간으로 찾을 수 있다는 특징이 있다.

Set을 통해 구현하는 것과 이분 탐색을 직접 구현하는 것 두가지 방법으로 구현하였다.

<Set 컨테이너 사용>

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

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

	set<string> personSet;
	while (N--) {
		string str;
		cin >> str;
		personSet.insert(str);
	}	

	vector<string> result;
	while (M--) {
		string str;
		cin >> str;

		set<string>::iterator iter = personSet.find(str);
		if (iter != personSet.end())
			result.push_back(*iter);
	}

	sort(result.begin(), result.end());

	cout << result.size() << '\n';
	for (auto x : result)
		cout << x << '\n';

	return 0;
}

<Binary_search & sort 직접 구현>

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

void swap(vector<string>& v, int idx1, int idx2) {
	string temp = v[idx1];
	v[idx1] = v[idx2];
	v[idx2] = temp;
}
void swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

int getMidIndex(vector<string>& v, int start, int end) {
	int mid = (start + end) / 2;
	int idx[3] = { start, mid, end };

	if (v[idx[0]] > v[idx[1]])
		swap(idx, 0, 1);
	if (v[idx[1]] > v[idx[2]])
		swap(idx, 1, 2);
	if (v[idx[0]] > v[idx[1]])
		swap(idx, 0, 1);

	return idx[1];
}

void quick_sort(vector<string>& v, int left, int right) {
	if (left >= right) return;

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

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

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

		if (low > high)
			break;
		
		swap(v, low, high);
	}

	swap(v, pivot, high);
	quick_sort(v, left, high - 1);
	quick_sort(v, high + 1, right);
}

bool binary_search(vector<string>& personVector, string str) {
	int start = 0;
	int end = personVector.size() - 1;

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

		if (personVector[mid] == str)
			return true;
		else if (personVector[mid] < str)
			start = mid + 1;
		else
			end = mid - 1;
	}

	return false;
}

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

	vector<string> personVector;
	while (N--) {
		string str;
		cin >> str;
		personVector.push_back(str);
	}	
	quick_sort(personVector, 0, personVector.size() - 1);

	vector<string> result;
	while (M--) {
		string str;
		cin >> str;

		if (binary_search(personVector, str)) {
			result.push_back(str);
		}
	}
	quick_sort(result, 0, result.size() - 1);

	cout << result.size() << '\n';
	for (auto x : result)
		cout << x << '\n';

	return 0;
}

[문제 링크]

전체 그래프를 탐색하면서 아직 방문하지 않은 섬을 만나면 해당 섬의 좌표를 시작으로 하는 bfs를 수행하여 하나로 연결된 섬을 찾는다.

모든 좌표를 탐색했을 때 수행한 bfs 횟수가 곧 섬의 개수가 된다.

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

int w, h;
bool adj[50][50];
bool visited[50][50];
int dy[8] = { 0,0,-1,-1,-1,1,1,1 };
int dx[8] = { 1,-1,0,1,-1,0,1,-1 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if(nextY >= 0 && nextY < h && nextX >= 0 && nextX < w)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

int getIslandCount() {
	int cnt = 0;

	for(int y=0; y<h; y++)
		for (int x = 0; x < w; x++) {
			if (adj[y][x] && !visited[y][x]) {
				cnt++;
				bfs(y, x);
			}
		}

	return cnt;
}

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

	while (true) {
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;
		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				int n;
				cin >> n;
				adj[y][x] = n;
			}
		}
				
		cout << getIslandCount() << '\n';
	}

	return 0;
}

[문제 링크]

문제를 풀기 전에 연결 요소가 뭔지 알아야 할 필요가 있다.

연결 요소란? 그래프에서 하나로 연결된 정점들의 집합이라고 생각하면 된다.

그래프의 모든 정점을 방문할 때 까지 bfs나 dfs를 수행한 다음, 수행한 횟수가 곧 연결 요소의 갯수가 된다.

정점의 개수가 많고 양방향 그래프로 표현해야 하기 때문에 인접 행렬보단 인접 리스트로 그래프를 구현하는 것이 효율적이고 직관적이라고 생각한다.

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

int N, M;
vector<int> adj[1001];
bool visited[1001];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		for (int i = 0; i < adj[here].size(); i++) {
			int next = adj[here][i];
			
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

int getConnectedComponent() {
	int result = 0;

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			result++;
			bfs(i);
		}
	}

	return result;
}

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

	// 양방향 그래프로 구현할 것
	while(M--) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cout << getConnectedComponent() << endl;

	return 0;
}

[문제 링크]

수빈이가  위치한 좌표를 시작으로 +1 하는 경우, -1 하는 경우, *2 하는 경우 도달하는 좌표를 큐에 담는 방식으로 bfs를 수행하면 정답을 얻을 수 있다.

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

bool visited[100001];
int N, K;

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

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

		if (here == K) return sec;

		sec++;
		int next = here + 1;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
		
		next = here - 1;
		if (next >= 0 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}

		next = here * 2;
		if (next <= 100000 && !visited[next]) {
			q.push({ next, sec });
			visited[next] = true;
		}
	}

	// 이 행에 도달했다면 만나는건 불가능(가능성 0%)
	return -1;
}

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

	cout << bfs() << endl;
	
	return 0;
}

[문제 링크]

N,M의 최대값이 1000으로 꽤 큰편이기 때문에 그래프의 전체 탐색 횟수를 줄이기 위해 익은 토마토의 위치를 큐에 담아놓고 탐색하는 방법으로 구현하였다.

입력을 받을 때 안익은 토마토의 갯수를 카운팅하고 익은 토마토의 좌표를 큐에 담는다.

그 다음, 큐에 담긴 익은 토마토 좌표를 기준으로 동서남북을 확인하여 안익은 토마토를 찾아 해당 토마토를 익은 토마토로 바꾸고 큐에 담는다.

안익은 토마토의 갯수가 0이 되거나 새롭게 익은 토마토가 더이상 존재하지 않을 때까지 위 작업을 반복하면 된다.

안익은 토마토의 갯수가 0이 되었을때 반복한 횟수가 곧 최소 일수가 되며,

새롭게 익은 토마토가 더이상 존재하지 않을 때 안익은 토마토가 남아 있다면 토마토를 모두 익게 만드는 것은 불가능하다.

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

struct Pos {
	int y;
	int x;
};

// M: 가로, N: 세로
int M, N;
int adj[1000][1000];
int tomatoCnt;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };
queue<Pos> ripeTomatoQueue;

int getRipeTomatoDays() {
	int result = 0;

	while (tomatoCnt > 0) {
		if (ripeTomatoQueue.empty())
			return -1;

		result++;
		int qSize = ripeTomatoQueue.size();
		while (qSize--) {
			Pos herePos = ripeTomatoQueue.front();
			ripeTomatoQueue.pop();

			for (int i = 0; i < 4; i++) {
				Pos nextPos = { herePos.y + dy[i], herePos.x + dx[i] };
				
				if(nextPos.y >= 0 && nextPos.y < N && nextPos.x >= 0 && nextPos.x < M)
					if (adj[nextPos.y][nextPos.x] == 0) {
						adj[nextPos.y][nextPos.x] = 1;
						tomatoCnt--;
						ripeTomatoQueue.push(nextPos);
					}
			}
		}
	}

	return result;
}

int main(void) {
	cin.tie(0);

	cin >> M >> N;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> adj[y][x];
			Pos pos = { y,x };

			if (adj[y][x] == 0)
				tomatoCnt++;
			else if (adj[y][x] == 1)
				ripeTomatoQueue.push(pos);
		}
	}

	cout << getRipeTomatoDays() << endl;

	return 0;
}

[문제 링크]

간단한 그래프 탐색 문제였다.

그래프를 탐색하면서 배추가 있는 땅을 시작으로 하는 bfs를 수행하고 인접해 있는 배추를 방문 표시한다.

모든 좌표를 탐색했을 때 bfs 호출 횟수가 지렁이의 마리 수가 된다.

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

// M: 가로길이(x), N: 세로길이(y), K: 배추가 심어진 개수
int M, N, K;
bool adj[50][50];
bool visited[50][50];
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

struct Pos {
	int y;
	int x;
};

void bfs(int startY, int startX) {
	queue<Pos> q;
	q.push({ startY, startX });
	visited[startY][startX] = true;

	while (!q.empty()) {
		int hereY = q.front().y;
		int hereX = q.front().x;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M) {
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					q.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
			}
		}
	}
}

void dfsStack(int startY, int startX) {
	stack<Pos> stk;
	stk.push({ startY, startX });
	visited[startY][startX] = true;

	while (!stk.empty()) {
		int hereY = stk.top().y;
		int hereX = stk.top().x;
		stk.pop();

		for (int i = 0; i < 4; i++) {
			int nextY = hereY + dy[i];
			int nextX = hereX + dx[i];

			if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
				if (adj[nextY][nextX] && !visited[nextY][nextX]) {
					stk.push({ nextY, nextX });
					visited[nextY][nextX] = true;
				}
		}
	}
}

void dfsRecursion(int startY, int startX) {
	visited[startY][startX] = true;

	for (int i = 0; i < 4; i++) {
		int nextY = startY + dy[i];
		int nextX = startX + dx[i];

		if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < M)
			if (adj[nextY][nextX] && !visited[nextY][nextX]) {
				dfsRecursion(nextY, nextX);
			}
	}
}

int graphSearchAll() {
	int result = 0;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < M; x++) {
			if (adj[y][x] && !visited[y][x]) {
				result++;
				bfs(y, x);
				//dfsStack(y, x);
				//dfsRecursion(y, x);
			}
		}

	return result;
}

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

	while (tc--) {
		cin >> M >> N >> K;

		memset(adj, false, sizeof(adj));
		memset(visited, false, sizeof(visited));

		while (K--) {
			int x, y;
			cin >> x >> y;
			adj[y][x] = true;
		}

		cout << graphSearchAll() << endl;
	}

	return 0;
}