[백준 12886번] 돌 그룹 - 파이썬

문제 링크:

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

12886번: 돌 그룹

 

---

풀이 유형:

그래프 이론, 그래프 탐색, 너비 우선 탐색

 

★문제풀이 Point★

1. 총 돌의 개수는 고정이다. 

2. 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다.

 

풀이 과정:

이 문제는 강호가 모든 그룹에 있는 돌의 개수를 같게 만들려고 할 때 가능하면 1을, 불가능하다면 0을 출력하는 문제이다.

먼저 돌의 총합이 3의 배수가 되지 않으면, 어떠한 방식을 써도 모든 그룹에 돌의 개수를 같게 만들어 줄 수 없다.

이 문제의 핵심은 총 돌의 개수가 고정이라는 점이다. 굳이 파이썬에 있는 조합을 이용해 풀 필요가 없다. 3개 그룹이 존재하지만 3개 모두를 큐에 넣는 것이 아닌, 2개만 넣으면 나머지 1개는 전체 총합(total)에서 빼면 된다. 이렇게 하면 시간 복잡도 & 메모리 계산 감소가 된다.

너비 우선 탐색을 실행하여 두 그룹끼리 돌 개수를 비교하여 큐에 추가하고, 이를 큐가 빌 때까지 반복한다. 

만약 돌이 분배된 개수가 이전에 나온 적이 있었다면 해당 코드는 실행하지 않는다. 왜냐하면 똑같은 결과가 반복되어서 나올 것이기 때문이다. (중복 제거)

 

풀이 코드:

# 12886번 돌 그룹

from collections import deque

# 너비 우선 탐색 함수
def bfs():
    global a, b, c, total, visited
    q = deque()
    # 두 그룹 큐에 넣기
    q.append((a, b))
    # 방문 표시
    visited[a][b] = True
    # 큐가 빌 때까지 반복
    while q:
        x, y = q.popleft()
        # 총 돌의 개수는 항상 일정하므로 남은 그룹 돌 개수 계산 가능
        z = total - x - y
        if x == y == z:
            print(1)
            return
        # 두 그룹끼리 돌의 개수 비교
        for a, b in (x, y), (y, z), (x, z):
            if a < b:
                b -= a
                a += a
            elif a > b:
                a -= b
                b += b
            # 돌의 개수가 같은 그룹은 건너뛰기
            else:
                continue
            # 두 그룹이 돌을 분배한 후 남은 그룹의 돌 개수
            c = total - a - b
            # 가장 작은 값을 x, 가장 큰 값을 y로 받기
            x = min(a, b, c)
            y = max(a, b, c)
            # 중복 제거
            # 해당 돌의 개수만큼 아직 분배되지 않았다면
            if not visited[x][y]:
                # 분배 실시
                q.append((x, y))
                # 방문 표시
                visited[x][y] = True
    print(0)


# 돌의 정보 입력받기
a, b, c = map(int, input().split())
# 전체 돌의 개수
total = a + b + c
# 방문 표시
visited = [[False] * (total + 1) for _ in range(total + 1)]

# 총 돌의 개수가 3의 배수가 아니라면
if total % 3 != 0:
    # 같은 개수로 만들 수 없으므로 0 출력
    print(0)
# 3의 배수라면
else:
    # bfs 함수 실행
    bfs()

 

12886 돌 그룹