[ 백준 ][ 골드4 ] 12886번 - 돌 그룹 ( 파이썬 )

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

12886번: 돌 그룹

 

코드

---

def BFS(s):
    visited = [[False] * (total + 1) for _ in range(total+1)]
    a,b = s[0],s[1]
    Q = deque()
    Q.append((a,b))
    visited[a][b] = True
    while Q:
        x,y = Q.popleft()
        z = total - x - y
        if x == y == z:
            return True
        for v1,v2 in [(x,y),(y,z),(z,x)]:
            if v1 > v2:
                v1,v2 = v2,v1
            v2 = v2-v1
            v1 = 2*v1
            v3 = total - v1 - v2
            v1,v2 = max(v1,v2,v3),min(v1,v2,v3)
            if not visited[v1][v2]:
                visited[v1][v2] = True
                Q.append((v1,v2))

    return False

from collections import deque
s = sorted(list(map(int,input().split())))
total = sum(s)

if sum(s) % 3 != 0:
    print(0)
else:
    print(int(BFS(s)))

 

포인트

---

 

1. 시간초과를 방지하기 위해서는 방문처리를 두 개의 원소를 이용해야 한다.
2. 두 개의 원소로 나머지 한 원소를 알아낼 방법이 있다. 

 

풀이

---

| BFS |

• Queue에는 가장 큰 원소, 가장 작은 원소가 들어간다. 이유는 세 원소가 같아지려면 가장 큰 원소는 작아져야 하고 가장 작은 원소는 커져야 하기 때문이다.
• 돌의 총 개수는 정해져 있다. 따라서 큐에서 꺼낸 두 원소를 돌의 총 개수에서 빼면 나머지 원소를 찾을 수 있다.
• 세 원소의 값이 같아지는 것이 BFS를 끝내는 조건이다.
• 방문처리를 통해 Queue에 더이상의 값이 존재하지 않는다면 세 그룹을 같게 만들 수 없는 것이다.
• 또한 기본적으로 총 돌의 개수가 3으로 나뉘지 않으면 세 개의 그룹으로 똑같이 나눠질 수 없다.