문제

WolframAlpha, MATLAB과 같은 최신 소프트웨어는 수백만 개의 연립방정식을 빠른 시간 내에 풀어낼 수 있는 알고리즘을 갖추고 있다. 간단한 연립방정식을 푸는 프로그램을 직접 작성해 보자.

문제를 간단히 하기 위해, 모든 연립방정식은 ☆=◇ 형태로 주어진다. ☆이나 ◇ 자리에는 1000 이하의 자연수나 문자로 이루어진 변수가 들어갈 수 있다.

연립방정식의 해는 하나만 존재할 수도, 존재하지 않을 수도, 무한히 많이 존재할 수 있다는 점에 유의하라.

예시

  • 3=3, 1=1, x=2 3개 식으로 이루어진 연립방정식이 주어진 경우, 첫 번째 식과 두 번째 식은 의미가 없고, 세 번째 식에서 x=2라는 유일한 해를 얻어낼 수 있다.
  • 4=4, 5=a, a=3, b=a 4개 식이 주어진 경우, 두 번째 식과 세 번째 식이 서로 모순되기 때문에 해가 존재하지 않는다.
  • alpha=1, 1=alpha, beta=beta, gamma=alpha, 2=2 5개 식이 주어진 경우, 1번째 식과 4번째 식에서 alpha=1, gamma=1이라는 해를 얻어낼 수 있다. 다만 beta의 값은 어떠한 값을 넣어도 식이 성립하므로, 이 경우 해가 무한히 많이 존재한다.

관찰

어떻게 풀어야 할지 막막한 문제입니다만, 먼저 주어지는 식의 형태를 분석하면 다음 세 가지로 나뉨을 관찰할 수 있습니다.

  • “숫자=숫자”의 형태: 변수의 값에 대해서는 아무런 정보를 주지 않습니다. 두 숫자가 같은 경우에는 무시하면 되고, 두 숫자가 다른 경우에는 연립방정식의 해가 존재하지 않습니다.
  • “변수=숫자” 또는 “숫자=변수”의 형태: 변수의 해에 대한 정보를 직접적으로 전달하는 식입니다.
  • “변수=변수”의 형태: 변수의 해를 직접적으로 알려주지는 않지만, 두 변수의 값이 동일하다는 정보를 알려주므로 다른 식들을 통해 두 변수의 해를 유추할 수 있습니다.

2, 3번째 형태의 식에서 얻을 수 있는 정보를 통해 다음과 같은 성질을 유도해 봅시다.

  • “변수=숫자”, “숫자=변수” 형태의 식을 통해 일부 변수들의 해를 바로 알아냅니다.
  • “변수=변수” 형태의 식을 통해, 해를 알아낸 변수와 같은 값을 갖는 변수들의 해 또한 알아낼 수 있습니다. 이 과정에서, x=1, y=2, x=y와 같이 서로 모순되는 정보가 동시에 존재하는 경우 연립방정식의 해가 존재하지 않습니다.
  • x=y, y=z와 같이 변수들 간의 관계만 존재하고 실제 숫자와 연결되는 식이 존재하지 않는 경우 이 변수들은 무한히 많은 해를 가집니다.

따라서, 이 문제의 핵심적인 부분은 서로 같은 값을 가지는 변수들을 관리할 수 있는 자료구조를 구현하는 것임을 알 수 있습니다.

자료구조 기획

먼저, 단순한 구상으로만 존재하는 자료구조에 구체적으로 어떠한 기능이 필요한지 기획해 봅시다.

  • 자료구조에는 ‘변수’ 또는 ‘숫자’가 존재한다.
  • 서로 같은 값을 가지는 변수나 숫자들의 집합이 여러 개 존재한다.

예를 들어, x=1, y=z 2개의 식이 존재하는 경우를 생각해 봅시다. 이 상태는 서로 같은 변수와 숫자들의 집합인 {x, 1} 과 {y, z} 으로 요약할 수 있습니다. 이 상태에서 x=y라는 식이 추가되면 어떻게 될까요? 두 집합을 합쳐 {x, y, z, 1}라는 집합을 만드는 것이 자연스럽습니다.

  • 서로 다른 두 집합에 속한 변수나 숫자 간의 식이 추가될 경우, 두 집합을 합쳐 새로운 집합을 만든다.

이 상태에서 z=2라는 새로운 식이 추가된다고 생각해 봅시다. 그러면, 기존의 집합인 {x, y, z, 1}에 {2} 집합을 합쳐 {x, y, z, 1, 2}라는 집합을 만들어야 합니다. 그런데, 우리는 서로 같은 값을 가지는 변수와 숫자들을 집합에 넣기로 했는데, 1과 2는 같은 집합에 있을 수 없습니다. 따라서, 연립방정식의 해가 존재하지 않는 경우 또한 쉽게 구별할 수 있습니다.

  • 서로 다른 두 숫자가 한 집합에 존재할 경우 연립방정식의 해가 존재하지 않는다.

지금까지 정리한 자료구조의 기획안을 토대로, 문제에서 주어진 3번째 예제를 해결해 보도록 하겠습니다.

  • 연립방정식에 등장하는 변수와 숫자는 5개로, 처음에는 정보가 없기 때문에 모두 다른 집합에 속해 있습니다. {alpha}, {beta}, {gamma}, {1}, {2}
  • 첫 번째 식 alpha=1을 통해 {alpha}와 {1}을 합칩니다. {alpha, 1}, {beta}, {gamma}, {2}
  • 두 번째 식 1=alpha는 이미 alpha와 1이 같은 집합에 있기 때문에 넘어갑니다.
  • 세 번째 식 beta=beta는 이미 beta와 beta가 같은 집합에 있기 때문에 넘어갑니다.
  • 네 번째 식 gamma=alpha를 통해 {alpha, 1}과 {gamma}를 합칩니다. {alpha, gamma, 1}, {beta}, {2}
  • 다섯 번째 식 2=2는 같은 숫자 간의 식이기 때문에 넘어갑니다.
  • 최종 결과인 {alpha, gamma, 1}, {beta}, {2}를 통해 alpha=1, gamma=1이고 beta는 아무 값이나 될 수 있음을 알 수 있습니다. 연립방정식의 해가 존재하지 않는 경우 또한 직접 이 자료구조를 적용하여 해결해 보시기 바랍니다.

Union-Find 자료구조를 이용한 풀이

이처럼 겹치는 원소가 없는 집합(서로소 집합)들을 합쳐 나가는 연산을 수행하는 자료구조를 Union-Find라고 합니다. 앞서 살펴본 것처럼 Union-Find 자료구조는 다음과 같은 연산을 “매우 빠르게” 수행할 수 있습니다.

  • Union(X, Y): X가 속한 집합과 Y가 속한 집합을 합친다.
  • Find(X): X가 속한 집합이 무엇인지 알아낸다.

Union-Find 자료구조에서는 어떤 집합이 있을 때, 그 집합을 집합에 속한 특정한 원소를 통해 나타냅니다. 예를 들어, {x, y, z, a, 1}이라는 집합을 ‘집합 1’이라는 이름으로 나타내는 식입니다. 따라서, Find(x), Find(y), Find(1) 등의 연산을 수행하면 모두 1라는 결과를 얻어낼 수 있습니다. 두 집합을 합치는 Union 연산을 수행할 경우, 두 집합 중 한 집합이 자신의 이름을 버리고 상대 집합의 이름으로 합쳐지게 됩니다. 예시로, {x, y}라는 ‘집합 x’와 {z, 1}이라는 ‘집합 1’을 서로 합칠 경우, {x, y, z, 1}은 ‘집합 1’이 됩니다.

Union-Find 자료구조를 통해 식을 하나씩 처리하면서 집합을 합쳐 나가는 과정을 Union 연산을 통해 손쉽게 구현할 수 있습니다. 그렇다면, 마지막에 각 변수의 해를 찾는 것은 어떻게 하면 될까요?

먼저, x라는 변수의 해가 유일하게 존재하는 경우를 생각해 봅시다. 이 경우에는 {x, y, z, 1}처럼 x가 속한 집합에 숫자가 단 하나 존재해야 합니다. 그러면 그 숫자가 x의 해가 됩니다. 따라서, Find(x)와 어떤 숫자의 Find 결과가 동일하다면, x의 해를 알아낼 수 있습니다. x의 해가 무한히 많이 존재하는 경우는 {x, y, z}처럼 x와 같은 숫자를 알 수 있는 정보가 없는 경우입니다. 이 경우에는 Find(x)과 동일한 결과를 가지는 숫자가 존재하지 않습니다.

즉, 모든 변수와 숫자의 Find 연산 결과를 정리하여 각 변수의 해를 알아낼 수 있습니다.

해가 존재하지 않는 경우는 어떻게 찾을 수 있을까요? 이 경우는 {x, 1, 2}처럼 같은 집합에 서로 다른 숫자가 존재하는 경우입니다. 따라서, 서로 다른 숫자의 Find 결과가 같은 경우 연립방정식의 해가 존재하지 않습니다.

Tip. 변수를 이름으로 하는 집합(‘집합 x’)과 숫자를 이름으로 하는 집합(‘집합 1’)이 합쳐질 때, 무조건 숫자를 이름으로 하도록 하면 나중에 Find 연산을 통해 찾은 값이 바로 그 변수의 해가 되기 때문에 편리합니다.

Tip+. 두 집합이 모두 변수를 이름으로 하는 경우나 숫자를 이름으로 하는 경우는 우선순위가 중요하지 않습니다. 전자의 경우 정말로 상관이 없고, 후자의 경우 어차피 모순되는 경우이기 때문입니다.

지금까지의 내용을 정리하여, Union-Find 자료구조를 통해 이 문제를 푸는 알고리즘을 작성해 봅시다.

  • 초기화. 연립방정식에 등장하는 변수와 숫자들을 Union-Find 자료구조에 넣어 각각의 집합으로 만든다.
  • 식을 차례대로 보면서, ☆=◇라는 식이 등장하면, Union(☆,◇)를 통해 두 변수나 숫자가 속한 집합을 합친다.
  • 모든 식을 처리한 후, 각 변수와 숫자에 대해 Find 연산을 수행한다.
    • 변수의 경우, Find 연산을 통해 나온 결과가 숫자라면 그 숫자가 변수의 해가 된다. 변수라면 해가 존재하지 않는 경우이다.
    • 숫자의 경우, Find 연산을 통해 나온 결과가 반드시 자기 자신이어야 한다. 아닌 경우, 연립방정식의 해가 존재하지 않는다.

Union-Find 자료구조는 제대로 구현할 경우 연산을 매우 빠르게 수행할 수 있습니다. 일반적으로 Union 연산과 Find 연산 모두 상수 시간 O(1)에 동작한다고 간주합니다. 문제에서 주어진 식의 개수가 N이라면, 이 식에 등장하는 변수와 상수의 개수는 최대 2N개입니다. 위의 알고리즘에서 Union은 N번, Find는 최대 2N번 수행하기 때문에 이 알고리즘의 시간 복잡도는 O(N)임을 알 수 있습니다.

Union-Find 자료구조는 구현하기 매우 쉽고, 강력한 연산을 매우 빠르게 수행할 수 있기 때문에 문제해결 분야에서 반드시 알아야 하는 자료구조 중 하나입니다. 아래 글을 통해 Union-Find 자료구조의 구현 방법과 시간복잡도에 관해 더 알아보시기 바랍니다.

참고: Union-Find (Disjoint set) 자료구조

입력/출력 예제

입력 형식

  • 첫 번째 줄에는 방정식의 개수 N이 입력된다. (1 <= N <= 50,000)
  • 두 번째 줄에는 각 방정식들의 좌변 N개가 공백으로 구분되어 입력된다.
  • 세 번째 줄에는 각 방정식들의 우변 N개가 공백으로 구분되어 입력된다. (각 방정식의 양변에는 1000 이하의 자연수 또는 문자열이 입력된다.)

출력 형식

  • 첫 번째 줄에는, 연립방정식의 해가 존재하면 ‘YES’, 존재하지 않는다면 ‘NO’를 출력한다.
  • 해가 존재하는 경우, 두 번째 줄부터 각 줄에 방정식에 등장하는 변수와 그 해를 공백으로 구분하여 출력한다. 어떤 변수의 해가 무한히 많은 경우 해 대신 ?를 출력한다.

입력 예제 1

3
3 1 2
3 1 x

출력 예제 1

YES
x 2

입력 예제 2

4
4 5 a b
4 a 3 a

출력 예제 2

NO

입력 예제 3

5
1 alpha beta gamma 2
alpha 1 beta alpha 2

출력 예제 3

YES
alpha 1
beta ?
gamma 1

원문

Vlatko likes to play with integer arrays. He wrote two arrays of N elements on a piece of paper, each element being either a positive integer or a sequence of lowercase letters of the English alphabet representing a variable. A variable can be replaced with an arbitrary integer. It’s possible that both arrays contain the same variable or the same variable occurs multiple times in an array. If that’s the case, each occurence of the variable has to be replaced with the same integer in both arrays.

Vlatko wonders if it’s possible to replace all variables with some integer values in such a way that the two arrays become equal. Two arrays are considered equal if the numbers on the same positions in the arrays are equal.

출처

Croatian Open Competition in Informatics 2018/2019, Contest 1, #2(ZAMJENA)