[백준/12886/파이썬] 돌 그룹

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

12886번: 돌 그룹

Problem

• 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.
• A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

조건

• 첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)
• 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

SOL

생각보다 까다로운 문제였다.

 

시뮬레이션이긴 한데, 돌을 같은 개수로 만들 수 있으면 1의 조건은 a==b==c로 간단하지만, 단순히 Else라고 하기에는, 안되는 경우가 많을텐데, 그때마다 0을 출력할순 없다. 따라서,  "0"을 출력하는 조건을 생각해내기가 어려웟다.

그래서, while True의 무한반복으로 시뮬레이션 하는 방법은 적절하지 않다.

 

결국, 1시간 정도 생각하다가, 여러 블로그를 봤고 허탈한 결과가 있었다.

BFS/DFS는 3차원 배열으로 생각해야해서, 뛰어넘었는데, 사실 2차원으로 생각할 수 있는문제였다.

왜냐하면, A+B+C 의 합은 항상 일정하기 때문이다.(A->B ,B->C,A->C 등으로 돌이 옮겨가는거기 때문이다. 항상 총량은 같다) 즉, C는 총량 - A-B로 나타낼 수 있었고, 이 말은 곧 , C라는 변수는 필요가 없는 친구였다.

 

다음은, 탐색 도중, 중복되는 경우가 생기고 , 한가지 한가지의 경우에 대해서 어떻게 체크를 해줄거냐가 문제였다. 생각해보면, A,B에 따라서, C는 자동적으로 결정되고, A와 B의 총량은 합계만큼(최대)될 수도 있기 때문에, visited(방문) 배열을 total만큼 선언해준다. 그리고, X,Y를 정해야 하는데, X,Y가 똑같은 경우가 또 나올 수 있기 때문에, X,Y는 최댓값, 최솟값을 넣어주어 중복을 피해주었다.

 

#시뮬레이션
from collections import deque

def bfs():
    dq = deque()
    dq.append((A,B))
    visited[A][B] = True
    while dq:
        x,y = dq.popleft()
        z = total-x-y
        if x==y==z:
            print(1)
            return
        for a,b in (x,y),(x,z),(y,z):
            if a<b:
                b-=a
                a+=a
            elif a>b:
                a-=b
                b+=b
            else:
                continue
            # 중복되는 경우 제거 해주기.
            # X,Y의 경우에서 최대,최솟값만 기록해줌.q
            c=total-a-b
            X=min(a,b,c)
            Y=max(a,b,c)
            if not visited[X][Y]:
                dq.append((X,Y))
                visited[X][Y] = True
    print(0)

def sol():
    if total%3:
        print(0)
        return
    else:
        bfs()

A,B,C = map(int,input().split())
total=A+B+C
visited=[[False]*total for _ in range(total)]
sol()

 

간과한점

 A+B+C의 합은 일정하기 때문에, C는 total-A-B로 나타낼 수 있다. 즉, 변수 한개를 줄일 수 있게 되었다. 즉, Y에 있는돌을 X로 가져온다고 생각하면 되는거였다.