[ 문제 ]

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

[ 알고리즘 유형 ]

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

[ 정답 코드 ]

BFS

1)

from collections import deque
a,b,c = map(int, input().split())
visited = [[False]*1501 for _ in range(1501)]
tot = a+b+c
def dfs():
    global a,b,c
    q = deque()
    q.append([a,b])
    visited[a][b] = True
    while q:
        a,b = q.popleft()
        c = tot-a-b
        if a==b==c: 
            return 1
        for na, nb in ((a,b),(a,c),(b,c)):
            if na < nb:
                nb -= na
                na += na
            elif na > nb:
                na -= nb
                nb += nb
            else: continue
            nc = tot-na-nb
            a = min(min(na,nb), nc)
            b = max(max(na, nb), nc)
            if not visited[a][b]:
                q.append((a,b))
                visited[a][b] = True
    return 0
if tot%3 != 0: print(0)
else:
    print(dfs())

2)

from collections import deque, defaultdict
stones = list(map(int, input().split()))
visited = defaultdict(bool)
tot = sum(stones)
def dfs():
    q = deque([stones])
    visited[tuple(stones)] = True
    while q:
        a,b,c = q.popleft()
        if a==b==c: 
            return 1
        for x,y in ((a,b),(a,c),(b,c)):
            if x == y: continue
            elif x < y:
                y -= x
                x += x
            elif x > y:
                x -= y
                y += y
            z = tot-x-y
            if not visited[(x,y,z)] :
                visited[(x,y,z)] = True
                q.append([x,y,z])
    return 0
if tot%3 != 0: print(0)
else:
    print(dfs())
print(visited)
print(len(visited))

[ 풀이 방법 ]

첫 번째 풀이는 15011501만큼 리스트를 초기화시켜 방문체크를 했다.
a,b,c 3차원 리스트로 초기화 시키면 더 간단하게 풀이가 가능하다.하지만 메모리를 계산하면 15011501*1501로 2기가 바이트를 넘는다. 메모리제한이 512MB이기 때문에 3차원 리스트로 초기화한 풀이는 불가능하다.

두 번째 풀이는 defaultdict 딕셔너리를 이용하여 풀이하였다.

[ 풀이과정 이슈 ]

첫 번째 풀이는 나의 풀이이고
두 번째 풀이는 다른 사람의 코드를 참조하였다.

1501*1501 만큼의 리스트를 초기화하는 것보다 딕셔너리를 이용하는 것이 시간이 덜 걸릴 수 있겠는데? 라는 생각이 들었었다.

그러나 제출 후 시간을 확인해보니 시간차이가 엄청났다.

나의 생각과 달리 2차원리스트를 이용한 방법이 훠얼씬 시간이 덜 걸렸다.