돌 그룹 (12886번) - 백준 (BOJ)

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

12886번: 돌 그룹

 

 

백준 - 돌 그룹 (12886번)

 

난이도 : Gold 4

알고리즘&자료구조 : BFS (너비 우선 탐색)

---

★ 핵심 Idea ★

 

◎ 주어진 초기 숫자 3개로 시작해서, 3개의 수가 모두 같아질 때까지 BFS를 활용해 연산을 진행해본다.

 

 

< 전체 코드 >

 

class Rocks():
    def __init__(self, A, B, C):
        self.is_eq = 0
        if A==B==C:
            self.is_eq = 1
        elif not (A+B+C)%3:
            start = tuple(sorted([A, B, C]))
            self.visited = {start}
            queue = [start]
            self.tmp = []
            while not self.is_eq and queue:
                for A, B, C in queue:
                    if B < C:
                        self._calc(C, B, A)
                        if A < B:
                            self._calc(C, A, B)
                    else:
                        self._calc(B, A, C)
                queue = self.tmp
                self.tmp = []

    
    def _calc(self, big, small, other):
        big, small = big-small, small<<1
        if big == small == other:
            self.is_eq = 1
        else:
            seq = tuple(sorted([big, small, other]))
            if seq not in self.visited:
                self.visited.add(seq)
                self.tmp.append(seq)


if __name__ == '__main__':
    rocks = Rocks(*map(int, input().split()))
    print(rocks.is_eq)