[백준][Python]12886번(돌 그룹)

백준 12886번

✔️ 문제 풀이

◾ bfs & 딕셔너리 활용

• 문제 자체는 어렵지 않으나 방문체크를 안 해주면 시간초과 발생

처음 제출한 코드

from collections import deque

a, b, c = map(int, input().split())

def check(a, b, c):
  if a==b==c:
    return True
  return False

def bfs(a, b, c):

  visited = dict()
  queue = deque()
  queue.append((a, b, c))
  visited[(a, b, c)] = 1

  while queue:

    a, b, c = queue.popleft()

    if check(a, b, c):
      return 1

    if a > b:
      a_ = a-b
      b_ = b+b
      if a_ > 0 and (a_, b_, c) not in visited:
        visited[(a_, b_, c)] = 1
        queue.append((a_, b_, c))
    elif b > a:
      a_ = a+a
      b_ = b-a
      if b_ > 0 and (a_, b_, c) not in visited:
        visited[(a_, b_, c)] = 1
        queue.append((a_, b_, c))
    if b > c:
      b_ = b-c
      c_ = c+c
      if b_ > 0 and (a, b_, c_) not in visited:
        visited[(a, b_, c_)] = 1
        queue.append((a, b_, c_))
    elif c > b:
      b_ = b+b
      c_ = c-b
      if c_ > 0 and (a, b_, c_) not in visited:
        visited[(a, b_, c_)] = 1
        queue.append((a, b_, c_))
    if a > c:
      a_ = a-c
      c_ = c+c
      if a_ > 0 and (a_, b, c_) not in visited:
        visited[(a_, b, c_)] = 1
        queue.append((a_, b, c_))
    elif c > a:
      a_ = a+a
      c_ = c-a
      if c_ > 0 and (a_, b, c_) not in visited:
        visited[(a_, b, c_)] = 1
        queue.append((a_, b, c_))

  return 0

if (a+b+c)%3: print(0)
else: print(bfs(a, b, c))

✔️ 다른 풀이

◾ 방문체크에 활용하는 자료구조를 2차원 배열로 변경

• 원소의 개수는 3개로 고정이며, 원소 3개의 합도 일정함으로 두 개 쌍에 대해서만 방문체크를 해줘도 된다. (나머지 한 개 원소의 값은 전체 합에서 두 개의 값을 빼면 알 수 있음)
• 이렇게 하면 세 개 원소의 값을 튜플로 저장하여 그 튜플 값을 딕셔너리의 키 값으로 쓰는 것보다 훨씬 시간이 절약된다.

참고한 코드

import collections


def bfs(a, b, c):
    q = collections.deque()
    q.append([a, b, c])
    V[a][b] = 1
    while q:
        a, b, c = q.popleft()
        if a == b and b == c and c == a:
            return 1
        if a > b and not V[a - b][2 * b]:
            V[a - b][2 * b] = 1
            q.append((a - b, 2 * b, c))
        elif a < b and not V[2 * a][b - a]:
            V[2 * a][b - a] = 1
            q.append((2 * a, b - a, c))
        if b > c and not V[b - c][2 * c]:
            V[b - c][2 * c] = 1
            q.append((a, b - c, 2 * c))
        elif b < c and not V[2 * b][c - b]:
            V[2 * b][c - b] = 1
            q.append((a, 2 * b, c - b))
        if c > a and not V[2 * a][c - a]:
            V[2 * a][c - a] = 1
            q.append((2 * a, b, c - a))
        elif c < a and not V[a - c][2 * c]:
            V[a - c][2 * c] = 1
            q.append((a - c, b, 2 * c))
    return 0

A, B, C = map(int, input().split())
V = [[0] * 1500 for _ in range(1500)]
print(bfs(A, B, C))