[학습 3회차] union find & 카카오 페스티벌 문제 C 숏코딩

오늘은 학습 동아리 활동으로 문제 풀기에 앞서 문제 풀이에 필요한 개념인 union find에 대해 공부를 해보려고 한다.

우선, 문제 풀이에 앞서서 예선 문제 C '숏코딩' 문제가 어떤 문제인지를 먼저 파악해 볼 예정이다.

 

문제가 항상 그렇듯이 길기 때문에 내가 나중에 보았을 때도 잘 알아들을 수 있도록 아래와 같이 정리한다.

 

[문제 정리]

라이언이 짠 프로그램은 조건문 S를 작성하면 그 조건문의 동치가 간략화되어서 나온 S'를 출력하도록 하는 문제이다.

규칙은 아래와 같다.

 

1. 변수 이름은 영문 알파벳으로만 구성되어 있다.

2. 변수는 값을 저장하고 있으며, 변수의 값은 정수 값을 의미한다. (범위는 -10의 9승 ~ 10의 9승 이하이다.)

3. 연산자는 두 개이다. == 와 != 가 있다. 각각의 경우 참이면 true 거짓이면 false를 반환한다. 이 연산자들의 경우 좌변과 우변에는 오직 '단항식'만 올 수 있다.

4. 논리 곱 연산자 && 로 한 개 이상의 논리식들을 연결하여 조건문을 만들게 된다.

 

이러한 방법으로 조건 식을 만들게 되고, 간단하게 말해서 길이가 긴 S 조건문 대신에 동치인 S'를 구해주는 프로그램을 작성하면 된다. 예시는 아래와 같다. 백준 사이트에 있던 것을 그대로 가져왔다.

 

festival==kakao&&festival==2018&&haha==123456&&hoho!=123456

이 식이 S이고,

festival==2018&&kakao==2018&&haha==123456&&hoho!=haha

이 식이 S' 즉 도출해야 할 목표가 되는 셈이다.

 

이전에 union find를 알고리즘 수업시간에 다룬 경험이 있다. 그 경험을 바탕으로 간단하게 union find를 짚고 넘어가면 아래와 같다.

 

집합을 구현할 때 가장 효율적인 트리 구조를 이용하여 구현하는 것으로, 세 가지 연산을 사용하게 된다.

1. make-set(x): 초기화를 할 때 사용되며, x를 유일한 원소로 하는 새로운 집합을 만든다.

2. union(x, y): 합하기, x가 속한 집합과 y가 속한 집합을 합친다. 두 집합을 합치는 연산이다.

3. find(x): 찾기, x가 속한 집합의 대표값을 반환한다. x가 어떤 집합에 속해있는지를 찾는 연산이다.

 

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

이 블로그를 참고해서, 다시 한 번 정리를 해 보았다. 그 결과, 나는 이 문제를 이렇게 풀면 어떨까, 하고 정리를 해 보았다. 우선, 위의 예제를 예시로 들어본다면 이와 같이 생각을 해 보았다.

 

위의 식을 예로 들어보자. 각각의 문장들을 ==나 !=그리고 &&가 나올 때로 각각 처리를 한다고 생각해보자.

 

-> festival == kakao

festival을 읽었을 때, 아무런 트리도 생성되지 않았으므로, make-set(x)을 해서 빈 루트에 자식으로 festival을 생성한다.

그리고 나서 ==를 읽게 되면, 빈 루트에 값으로 ==을 넣어준다. 

그다음 kakao라는 글을 읽고 나면 이 단어가 기존의 트리에 존재하는지 find(x)를 사용하여 찾는다. 반환 값이 0이라면 기존의 트리에서 같은 값이 없는 것이므로 이 값이 나오면 == 루트에 자식으로 kakao 값을 넣는다.

 

-> &&

그 다음 &&을 마주하게 되면, 새로운 트리를 생성할 준비를 한다. &&값을 0에서 1이 될 수 있도록 ++을 해준다.

 

-> festival == 2018

다음 읽은 festival이라는 값을 find(x)를 통해 존재하는지 찾는다. 존재한다면 존재하는 값의 루트의 값 (==)를 반환할 것이다. 반환 값이 0이 아니라면 이미 트리에 존재하는 값이므로, 따로 이에 대한 트리를 생성하거나 하지 않고 keep해 둔채 다음 연산자를 확인한다. 이 때, 연산자가 방금 반환된 루트의 값과 같다면 (==이라면) 새로운 트리를 생성하지 않고, 만일 !=이라면 새로운 트리를 생성한다. 

그러나 이 문제에서는 반환된 루트의 값과 읽은 값이 같으므로 새로운 트리를 생성하지 않고 다음 값으로 넘어간다.

다음 값은 2018이다. 그러나, 새로운 트리가 생성되지 않았으므로, 기존 트리에 2018값을 가진 자식을 만들어 추가한다.

 

다음 나오는 && 값은 이전의 설명과 동일하다.

 

-> haha == 123456

이전의 방식과 유사하게, haha가 기존의 트리에 있는 값인지 확인하고 없다면 새로운 트리를 만든다.

새로 만들어진 트리의 root값에는 == 연산자를 넣어주고, 그 다음 읽은 값도 동일한 값이 아니라면 자식으로 추가를 해준다.

 

-> hoho != 123456

hoho도 역시 없는 값이다. 빈 루트의 자식으로 추가해주고 빈 루트에 이번에는 새로운 루트 값 != 연산자를 넣어준다. 그러나 다음이 문제이다. 123456은 이미 있는 값이고, find(x)를 해서 반환된 값이 속해있는 루트의 값이 ==로 나왔다. 하지만 현재 만들어진 트리의 루트 값과 일치하지 않으므로, 새로운 트리는 계속 유지가 되며, ==의 루트 값을 가지고 있는 123456의 값이 아닌 다른 자식의 값을 가지고 온다. (이 경우 자식은 분명히 2개만 있을 것이라고 예상한다.)

그리고 그 값을 123456대신에 haha의 값을 넣는다. 

 

이러한 과정을 거쳐 완성된 3개의 트리는 그림과 같다.

이 트리들을 각각 아래의 조건대로 만들면 우리가 구하고자 하는 S'가 나올 것이다.

 

1. 자식이 3개가 존재할 경우 숫자를 우선으로 두고, 식이 문자, 연산식, 숫자가 되도록 배치한다. 

2. 식의 좌항과 우항은 각각 단항식이며, 좌항 | 연산자 | 우항의 형식이 다 갖춰진 식이 하나 나오게 되면, 그 다음은 무조건 && 연산자를 출력한다.

 

트리의 입장으로 보면 자식1 | 루트 값 | 자식 3 && 자식1 | 루트 값 | 자식 2의 형식으로 만들어진다는 것이다.

festival==2018&&kakao==2018&&haha==123456&&hoho!=haha

 

정리하면 이러한 식이 만들어지는 것을 확인할 수 있다. 이러한 규칙을 지키면 나머지 예제도 문제 없을 것이라고 예상하며 방법을 생각해 보았다. 다음 시간에는 이와 같이 코드를 짜 볼 것이다.