취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3184번 문제인 양이다.
문제는 아래 링크를 확인하자.

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

'#'으로 구분되어 있는 각 영역마다 해당 영역의 양과 늑대의 마릿수를 셀 수 있다면 문제를 해결할 수 있을 것이다. 이는 BFS 등의 그래프 탐색 알고리즘을 이용하여 해낼 수 있다.

양과 늑대가 있을 수 없는 '.' 위치를 경계를 포함하여 양과 늑대가 없는 영역으로 생각하더라도 이러한 영역들은 문제의 답에 영향을 주지 않으므로 영역의 구분을 신경쓰면서 구현할 필요는 없다.

만약 '.'을 찾을 때마다 새로운 영역을 찾은 것으로 생각해 영역을 탐색하는 코드를 작성한다면 틀렸습니다를 받을 것이다. 모든 칸에 양 또는 늑대가 들어있는 영역이 존재할 수 있고 그러한 영역에는 '.'이 포함되어 있지 않기 때문이다.

아래는 제출한 소스코드이다.

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

int R, C;
string board[250];
int ocnt, vcnt;

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs(int qr, int qc) {
	int O = 0, V = 0;
	if (board[qr][qc] == 'o') O++;
	else if (board[qr][qc] == 'v') V++;
	board[qr][qc] = '#';
	
	queue<pair<int, int>> que;
	que.push(make_pair(qr, qc));
	
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == '#') continue;
			if (board[rr][cc] == 'o') O++;
			else if (board[rr][cc] == 'v') V++;
			board[rr][cc] = '#';
			que.push(make_pair(rr, cc));
		}
	}

	if (O > V) ocnt += O;
	else vcnt += V;
}

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

	cin >> R >> C;
	for (int r = 0; r < R; r++) cin >> board[r];

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] != '#') {
				bfs(r, c);
			}
		}
	}

	cout << ocnt << ' ' << vcnt;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1907번 문제인 탄소 화합물이다.
문제는 아래 링크를 확인하자.

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

주어진 형식의 문자열이 주어질 때, 첫번째, 두번째, 세번째 화학식을 구성하는 C, H, O의 개수를 구해두고 모든 가능한 계수의 쌍(1000가지이다.)에 대해 사전순으로 해당 계수가 주어진 식을 만족시키는지를 확인해 문제를 해결할 수 있다.

세 화학식은 '+'와 '='를 기준점으로 생각하면 간단하게 구분해낼 수 있다.

또한 이 문제에서 화학식에 주어지는 수는 항상 한자리이고 그 앞에는 그 대상인 원소가 등장하므로, 수가 등장할 때마다 바로 앞의 원소의 개수를 그 수에 맞게 추가하는 것으로 각 화학식을 구성하는 원소의 수를 계산할 수 있다.

아래는 제출한 소스코드이다.

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

int slen;
string s;
int pidx, eidx;

int c1, h1, o1, c2, h2, o2, c3, h3, o3;

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

	cin >> s;
	slen = s.length();

	for (int i = 0; i < slen; i++) {
		if (s[i] == '+') pidx = i;
		else if (s[i] == '=') eidx = i;
	}

	int ccnt = 0, hcnt = 0, ocnt = 0; char old = 'Z';

	for (int i = 0; i < pidx; i++) {
		if ('0' <= s[i] && s[i] <= '9') {
			if (old == 'C') ccnt += s[i] - '1';
			else if (old == 'H') hcnt += s[i] - '1';
			else ocnt += s[i] - '1';
		}
		else {
			if (s[i] == 'C') ccnt++, old = s[i];
			else if (s[i] == 'H') hcnt++, old =  s[i];
			else ocnt++, old = s[i];
		}
	}
	c1 = ccnt, h1 = hcnt, o1 = ocnt;

	ccnt = 0, hcnt = 0, ocnt = 0; old = 'Z';

	for (int i = pidx + 1; i < eidx; i++) {
		if ('0' <= s[i] && s[i] <= '9') {
			if (old == 'C') ccnt += s[i] - '1';
			else if (old == 'H') hcnt += s[i] - '1';
			else ocnt += s[i] - '1';
		}
		else {
			if (s[i] == 'C') ccnt++, old = s[i];
			else if (s[i] == 'H') hcnt++, old = s[i];
			else ocnt++, old = s[i];
		}
	}
	c2 = ccnt, h2 = hcnt, o2 = ocnt;

	ccnt = 0, hcnt = 0, ocnt = 0; old = 'Z';

	for (int i = eidx + 1; i < slen; i++) {
		if ('0' <= s[i] && s[i] <= '9') {
			if (old == 'C') ccnt += s[i] - '1';
			else if (old == 'H') hcnt += s[i] - '1';
			else ocnt += s[i] - '1';
		}
		else {
			if (s[i] == 'C') ccnt++, old = s[i];
			else if (s[i] == 'H') hcnt++, old = s[i];
			else ocnt++, old = s[i];
		}
	}
	c3 = ccnt, h3 = hcnt, o3 = ocnt;

	for (int i = 1; i < 11; i++) {
		for (int j = 1; j < 11; j++) {
			for (int k = 1; k < 11; k++) {
				if (i * c1 + j * c2 == k * c3 && i * h1 + j * h2 == k * h3 && i * o1 + j * o2 == k * o3) {
					cout << i << ' ' << j << ' ' << k;
					return 0;
				}
			}
		}
	}
}