백준 18847. Stray Cat (JOISC 2019/2020 Day 3 3번)

문제 설명(링크):

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

18847번: Stray Cat

문제 요약

투스텝 문제인데, 첫 번째 실행에는 그래프가 주어져서 그래프 간선에 $A$ 미만의 음이아닌 정수를 붙여야하고, 두 번째 실행에는 한 정점에서 시작하여 그래프는 주어지지 않고 그래프의 간선에 써진 정수값만 보여주어서 1번 정점에 도달하는 것이다. 또한, (1로 가는 최단경로) + $B$ 회 안에 도달해야 한다.

 

풀이

서브테스크 1~4 $(A=3)$

별로 어렵지 않다. 기본적인 아이디어는 BFS Tree인데, BFS 돌리면서 트리를 만들면 모든 간선이 잇는 두 정점의 깊이차이는 1 이하이다. 따라서 깊이가 $3k+a$, $3k+a+1$인 정점을 잇는 간선에는 $a$를 대응시켜주면 되고, 깊이가 같은 두 정점을 잇는 간선은 그 정점의 깊이를 3으로 나눈값을 대응시켜주면 된다.(1의 깊이는 0)

 

서브테스크 5~7 (그래프가 트리, $A=2, B=6$)

일단, 모든 리프 제외 정점의 차수가 3 이상이라 해보자. 그러면 쉽게 풀리는데, 홀수 깊이의 정점에서 아래로 뻗어나가는 간선에는 0, 짝수 깊이는 1을 붙이면, 한 정점에서 간선에 붙은 레이블의 집합은 0 한개 이하, 1여러개 이거나, 1 한개 이하, 0여러개 이런식으로 되어 있다. 그러면 부모 쪽으로 가야 하니 한 번만 등장한 레이블이 적힌 곳으로 가면 된다. 문제는 차수가 정확히 2인 정점인데 이 경우는 0이 적힌 간선과 1이 적힌 간선이 정확히 하나 있으므로 자신이 부모 쪽으로 가고있는지, 자손 쪽으로 내려가고 있는지 알 수가 없다.

 

하지만, $B$값에서 힌트를 줬듯이 연속 3번으로 차수가 2인 정점이 나왔을 때 자신이 자손 쪽으로 가고 있는지 부모 쪽으로 가고있는지 알 수 있도록 정보를 줄 수 있다. 일단, 일자형 트리를 생각해 보자. 일자형 트리의 간선에 순서대로 1, 1, 0, 1, 0, 0을 차례로 배치한다. (110100110100110100.... 이런식으로 적히게 된다) 이 문자열의 특징은 임의의 길이 5인 부분문자열에 대해 앞으로 읽는것과 뒤로 읽는것이 시작점과 무관하게 항상 다르다는 것이다. 이를 직선형 트리에 배치했다면, 쉽게 문제를 해결할 수 있다. 일단 처음 3번은 아무 방향을 정해 직진한다. 그러면, 연속된 문자 5개를 알 수 있다. 그러면, 현재까지 올바른 방향으로 가고 있었는지 아니었었는지도 알 수 있다. 이렇게 한번 방향이 정해지면, 계속 따라 올라가면 된다.

 

일반 트리에서도 다르지 않다. DFS를 돌면서 차수가 2인 연속된 체인이 등장할 때마다 저 문자열을 붙이면 되고, 그렇지 않으면 1, 0을 번갈아 쓰면 된다.

 

소스코드

#include "Anthony.h"
#include "Catherine.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef int ll;

#define MAX 101010

namespace {
	vector<ll> adj[MAX], num[MAX], depth, deg, arr;
	vector<ll> ret;
	ll asdf[6] = { 1, 1, 0, 1, 0, 0 };
	void dfs(ll x = 0, ll p = -1, ll d = 1, ll str = 0, ll chk = 0) {
		depth[x] = d;
		ll i;
		for (i = 0; i < (int)adj[x].size(); i++) {
			if (adj[x][i] == p) continue;
			if (deg[adj[x][i]] == 2) {
				if (!chk) {
					while (d != asdf[str % 6]) str++;
				}
				ret[num[x][i]] = asdf[str % 6];
				dfs(adj[x][i], x, !asdf[str % 6], str + 1, 1);
			}
			else {
				ret[num[x][i]] = d;
				dfs(adj[x][i], x, !d);
			}
		}
	}
	void bfs() {
		queue<pair<ll, ll>> q;
		q.push({ 0, 0 });
		while (!q.empty()) {
			pair<ll, ll> t;
			t = q.front();
			q.pop();
			ll v = t.first;
			if (arr[v] != -1) continue;
			arr[v] = t.second;
			for (auto x : adj[v]) {
				q.push({ x, (t.second + 1) % 3 });
			}
		}
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
	if (A != 2) {
		ll i;
		for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
		for (i = 0; i < M; i++) num[U[i]].push_back(i);
		for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
		for (i = 0; i < M; i++) num[V[i]].push_back(i);
		ret.resize(M);
		arr.resize(N);
		for (i = 0; i < M; i++) ret[i] = -1;
		for (i = 0; i < N; i++) arr[i] = -1;
		bfs();
		for (i = 0; i < M; i++) {
			if (arr[U[i]] == arr[V[i]]) ret[i] = arr[U[i]];
			else {
				ll u, v;
				u = min(arr[U[i]], arr[V[i]]);
				v = max(arr[U[i]], arr[V[i]]);
				if (u == 0 && v == 1) ret[i] = 0;
				if (u == 1 && v == 2) ret[i] = 1;
				if (u == 0 && v == 2) ret[i] = 2;
			}
		}
		return ret;
	}
	ret.resize(M);
	deg.resize(N);
	ll i;
	for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
	for (i = 0; i < M; i++) num[U[i]].push_back(i);
	for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
	for (i = 0; i < M; i++) num[V[i]].push_back(i);
	for (i = 0; i < M; i++) deg[U[i]]++, deg[V[i]]++;
	depth.resize(N);
	dfs();
	return ret;
}

namespace {

int A, B;
int variable_example = 0;
ll pv;
ll str;
ll last;
string up[6], down[6];

bool chk(string s) {
	for (ll i = 0; i < 6; i++) {
		if (s == up[i]) return true;
	}
	return false;
}

string s;

}  // namespace

void Init(int A, int B) {
	::A = A;
	::B = B;
	pv = -1;
	str = 0;
	last = 0;
	up[0] = "00101";
	up[1] = "01011";
	up[2] = "10110";
	up[3] = "01100";
	up[4] = "11001";
	up[5] = "10010";
}

int Move(std::vector<int> y) {
	if (A != 2) {
		if (y[0] && y[1]) return 0;
		if (y[1] && y[2]) return 1;
		if (y[2] && y[0]) return 2;
		if (y[0]) return 0;
		if (y[1]) return 1;
		if (y[2]) return 2;
	}
	if (pv != -1) {
		if ((y[0] + y[1] + 1) != 2) {
			str = 0;
			s.clear();
			last = 1;
			y[pv]++;
			if (y[0] == 1) {
				if (pv == 0) return -1;
				else return pv = 0;
			}
			else {
				if (pv == 1) return -1;
				else return pv = 1;
			}
		}
		else {
			if (!last) {
				str++;
				ll nxt;
				if (y[0]) nxt = 0;
				else nxt = 1;
				s.push_back(nxt + 48);
				if (str == 5) {
					if (chk(s)) {
						last = 1;
						str = 0;
						s.clear();
						return pv = nxt;
					}
					else {
						last = 1;
						str = 0;
						s.clear();
						return -1;
					}
				}
				else {
					return pv = nxt;
				}
			}
			else {
				if (!(y[0] + y[1])) return -1;
				if (y[0]) return pv = 0;
				else return pv = 1;
			}
		}
	}
	else {
		if ((y[0] + y[1]) != 2) {
			last = 1;
			if (!(y[0] + y[1])) return -1;
			if (y[0] == 1) return pv = 0;
			else return pv = 1;
		}
		else {
			if (y[0] == 2) {
				s.push_back('0');
				s.push_back('0');
				str += 2;
				return pv = 0;
			}
			else if (y[1] == 2) {
				s.push_back('1');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
			else {
				s.push_back('0');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
		}
	}
}

백준이라서 두 소스코드를 합쳐서 냈다.