BOJ 2593 - 엘리베이터

i번째 엘리베이터를 수식으로 나타낸다면 첫 위치를  그리고 몇칸씩 이동할 수 있는지를 로 표현한다면 i번째 엘리베이터가 갈 수 있는 곳은 아래를 만족하는 모든 층에 갈 수 있다.

하지만 최고층이 N이기 때문에 y는 최대 N까지 밖에 갈 수 없다. 따라서 엘리베이터에 따라 k의 최대값이 달라진다.

모든 엘리베이터를 수식으로 두고, 서로 다른 두 엘리베이터에 대해 i에서 j로 갈 수 있는지를 판단한다. 만약 i 엘베에서 j 엘베로 갈 수 있다면 간선을 연결해준다. 

이 때 간선을 연결해줄 알고리즘이 매우 까다롭다. 두 수식에 대해서 만족하는 해와 최대층 N에 대해서 처리를 해줘야하기 때문이다.

우선 두 수식을 아래처럼 나타낸다.

이제 꼴로 나타냈으니 수식의 해가 정수해이기 위해선(정수해인 이유는 엘베에 대해 한층 올라가는 것은 실수가 아니라 정수이기 때문) 가 일단 에 대해 나눠떨어져야 확장 유클리드를 사용할 수 있다. 나눠떨어지지 않는다면 정수해가 존재하지 않기 때문에 바로 종료, i와 j 간의 간선을 생성해주지 않는다.

만약 나눠떨어졌다면, 를 로 두고, 마지막인 x를 빼버렸다고 생각하고 확장 유클리드를 구한다. 나중에 확장 유클리드를 구한 해가 (x1, y1)이였다면 우리가 실재로 구해야하는 해는 (x1*x, y1*x)가 된다.

확장 유클리드를 이용하여 두 해에 대해 가장 작은 음이 아닌 정수의 짝을 찾고, 두 수식에 대입하여 N층을 넘어가는지 판단한다. 이는 곧 두 엘베가 같은 층에 멈출 수 있는 곳을 찾는 것이고 최대층이 N이므로 같은 층에 멈추는 가장 낮은 층이 N을 넘어가면 간선을 이어주지 못하는 것이다.

만약 이 값도 N보다 작다면 i번째 엘베에서 j번째 엘베로 이동이 가능하단 소리다.

다음으로 A와 B에 대해서 이용할 수 있는 모든 엘리베이터를 조사한다. 이는 단순 나머지 연산과 시작점을 이용하여 구할 수 있다.

나머지는 BFS로 해결한다. A층에서 탈 수 있는 모든 엘베를 BFS로 각각 돌리고, BFS 결과에 따라 B층으로 갈 수 있는 모든 엘베에 대해 가장 짧은 것을 찾는다. 이 과정은 네트워크 플로우를 응용해서 작성했다. 이전에 있던 값을 조사해야하기 때문에 이처럼 작성했다.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
int abs_v(int a) { return a < 0 ? -a : a; }
int N;
int gcd(int a, int b) {
	int t;
	while (b) { t = a%b; a = b; b = t; }
	return a;
}
bool ex_euclid(int a, int b,int sbsa, int sb, int sa) {
	int r0 = a, r1 = b, s0 = 1, s1 = 0, t0 = 0, t1 = 1,q,r,s,t;	
	while (r1) {
		q = r0 / r1;
		r = r0 - q*r1;
		if (r < 0) {
			r0 -= r1;
			q = r0 / r1;
			r += r1;
		}
		r0 = r1; r1 = r;
		s = s0 - q * s1;
		s0 = s1; s1 = s;
		t = t0 - q * t1;
		t0 = t1; t1 = t;
	}
	s0 *= sbsa / r0;
	t0 *= sbsa / r0;
	int lcm = (-a)*b / r0,aa = lcm/(-a),bb = lcm/b;
	while (s0 < 0 || t0 < 0) s0 += aa, t0 += bb;
	while (s0 - aa >= 0 && t0 - bb >= 0) s0 -= aa, t0 -= bb;

	s0 %= b, t0 %= (-a);
	int ea = b*t0 + sb, eb = (-a)*s0+sa;
	return ea <= N && eb <= N;
}

int main1() {
	N = 20;
	int a, b, s1, s2,g;
	a = 3, b = 8;
	s1 = 1, s2 = 12;
	g = gcd(a, b);
	if ((s2 - s1) % g == 0) {
		if (s2 > s1) ex_euclid(-b, a,s2-s1, s1,s2);
		else ex_euclid(-a , b ,s1-s2, s2,s1);
	}	
	return 0;
}

int main() {
	int M, A, B, ev[100][2], i, j, a, b, c, vi[100], u, f = 1,mini=1e9,sa,sb,g,uv;
	scanf("%d%d", &N, &M);
	vector<vector<int>> adj(M);
	vector<int> src, sink;
	stack<int> ans;
	for (i = 0; i < M; i++) {
		scanf("%d%d", &ev[i][0], &ev[i][1]);
		for (j = 0; j < i; j++) {
			a = ev[j][1], b = ev[i][1];
			sa = ev[j][0], sb = ev[i][0];
			c = sb-sa;
			g = gcd(a, b);
			uv = 0;
			if ((sb - sa) % g == 0) {
				if (sb > sa) uv = ex_euclid(-b, a, sb - sa, sa,sb);
				else uv = ex_euclid(-a, b, sa - sb, sb,sa);
			}
			if (uv) {
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	scanf("%d%d", &A, &B);
	for (i = 0; i < M; i++) {
		if (A - ev[i][0] >= 0 && (A - ev[i][0]) % ev[i][1] == 0) src.push_back(i);
		if (B - ev[i][0] >= 0 && (B - ev[i][0]) % ev[i][1] == 0) sink.push_back(i);
	}
	if (A == B) mini = 0;
	queue<int> q;
	for (int s : src) {
		memset(vi, -1, sizeof(vi));
		q.push(s);
		while (!q.empty()) {
			u = q.front(), q.pop();
			for (int v : adj[u])
				if (vi[v] == -1) {
					vi[v] = u;
					q.push(v);
				}
		}
		for (int t : sink) {
			if (vi[t] == -1) continue;
			stack<int> trace;
			for (i = t; i != s; i = vi[i])
				trace.push(i);
			trace.push(s);
			if (trace.size() < mini) {
				mini = trace.size();
				ans = trace;
			}
			f = 0;
		}
	}
	
	if (f) printf("-1");
	else {
		printf("%d\n", ans.size());
		while (!ans.empty()) {
			printf("%d\n", ans.top()+1); ans.pop();
		}
	}
	
	return 0;
}