취미로 코딩하기

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

이번에 볼 문제는 백준 2708번 문제인 폴리큐브의 겉넓이이다.
문제는 아래 링크를 확인하자.

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

주어지는 큐브들을 순서대로 읽어나가면서, 이전에 등장한 큐브들과 인접한 위치에 새 큐브를 연결하려고 시도하는지를 체크해 주어지는 입력이 폴리큐브를 제대로 생성하는지를 우선 확인하자. 각 문자열을 좌표로 파싱할 때 두 콤마(',')의 위치를 확인해두고 substr과 stoi를 이용하면 편하게 파싱할 수 있다.

다음으로 연결하고자 하는 큐브가 기존에 연결된  큐브들과 인접한지를 확인하는 것은 입력받은 큐브들의 좌표를 set에 저장하고 새로 입력받은 큐브의 6방위 좌표중 적어도 하나가 set에 포함되어있는지를 확인하는 것으로 해낼 수 있다. 이 때 아래 코드의 dx,dy,dz와 같은 배열을 활용하면 구현을 더욱 편리하게 할 수 있다. 이미 입력이 들어온 큐브를 또다시 입력받는 것도 잘못된 입력이므로 이 또한 예외처리해주자.

폴리큐브의 겉넓이는 각 폴리큐브에 대하여 6방위 좌표중 연결된 큐브가 없는 면의 수를 세는 것으로 계산가능하다는 점을 관찰하자.

첫 큐브의 위치는 (0,0,0)으로 주어짐을 assert문으로 확인해뒀으니 구현에 참고하자.

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

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

int T, N;

int X[1000], Y[1000], Z[1000];

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

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

	cin >> T;
	while (T--) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			vector<int> pos;
			string s; cin >> s;
			int slen = s.length();
			for (int i = 0; i < slen; i++) {
				if (s[i] == ',') pos.emplace_back(i);
			}
			int& pos1 = pos[0], & pos2 = pos[1];

			X[i] = stoi(s.substr(0, pos1));
			Y[i] = stoi(s.substr(pos1 + 1, pos2 - pos1 - 1));
			Z[i] = stoi(s.substr(pos2 + 1, slen - pos2 - 1));
		}

		set<pair<pair<int, int>,int>> st;
		st.insert(make_pair(make_pair(X[0], Y[0]), Z[0]));

		bool chk = 1;
		for (int i = 1; i < N; i++) {
			bool connected = 0;
			for (int k = 0; k < 6; k++) {
				if (st.count(make_pair(make_pair(X[i] + dx[k], Y[i] + dy[k]), Z[i] + dz[k]))) connected = 1;
			}

			auto p = make_pair(make_pair(X[i], Y[i]), Z[i]);

			if (!connected || st.count(p)) {
				cout << "NO " << i + 1 << '\n';
				chk = 0;
				break;
			}
			
			st.insert(p);
		}

		if (chk) {
			int ans = 0;
			for (auto& p : st) {
				int x = p.first.first, y = p.first.second, z = p.second;
				for (int k = 0; k < 6; k++) {
					if (!st.count(make_pair(make_pair(x + dx[k], y + dy[k]), z + dz[k]))) ans++;
				}
			}

			cout << ans << '\n';
		}
	}
}