[BFS] 백준 12886번 : 돌 그룹 - 파이썬 Python (보충예정)

 

 

생각하기

돌 그룹이 모두 같은 개수가 있는지를 찾는 문제이기 때문에 DFS 와 BFS 중 고민했다.

최소를 구하는 문제는 아니지만 그룹의 개수가 같아지면 바로 프로그램을 종료하면 된다고 생각했다

만약 DFS를 사용한다면 그게 그룹의 개수가 절대 같아지지 않는 경로를 탄다면 굉장히 오버헤드가 커질 것이라 생각했다

 

BFS로 A, B, C 조합의 주변부터 검사를 했을 때, 그룹의 개수가 같아지는 상황이 걸리면 바로 종료하기로 했다

 

구현하기

큐를 만들어서 해당 조합이 같지 않고 개수가 달라서 로직이 실행되고 

검사시, 문제가 없다면 큐에 넣어주어서 BFS를 구현한다

 

visited 배열

만약 조합이 이전에 했던 조합이 또 나오면 결국 그 안에서 반복되어 무한루프가 생기기 때문에 visited 여부를 체크해가며 BFS를 진행해야 한다

하지만 visited[A][B][C] 같은 3차원 배열(True/False)을 만든다면 문제가 있다.

A, B, C 초기값은 최대 500인데 최대 1000까지 갈 수 있다.

• 1000^3 x 4byte(int) = 4,000,000,000 = 4GB

이는 512MB (512,000,000)를 훨씬 초과하는 값이다.

 

그래서 이 부분에 대한 힌트를 얻었다

잘 보면 주요 로직이 결국 X 에서 Y를 빼고 Y를 두배해줌으로 결국 전체 합은 지속 유지되는 것이다

따라서 visited[A][B]로 표시해 주어도 문제가 없다

 

문제상황1

BFS를 짤 때 초기값에 대한 검사를 하지 않아서 틀렸습니다가 나왔다

초기에 입력되는 값에 대하여도 그룹들의 개수가 모두 같은지 검사를 하도록 하자

(이런 실수를 한두번 하는 것이 아니라서 나한테 하는 말이다)

큐에 이미 들어가 있는 값도 while 문에서 검사를 할 수 있도록 초반에 답에 대한 검사를 하는 로직을 배치하도록 하자!!!

 

문제상황2

시간 초과 문제 

해당 코드를 사용했을 때, 시간초과 문제가 발생하였다. 

import itertools
import copy
from collections import deque
# import sys
# input = sys.stdin.readline

group = list(map(int, input().split()))

s = sum(group)

visited = [[False]*(1501) for _ in range(1501)]

# dfs로 진행하면 안될 놈에게 계속 하게되는 함정이 있다


# 돌 그룹 개수가 같아지지 않다는 것을 알려면 어케?
    # --> 다시 원래 group으로 돌아온다? 아님 큐가 0가 된다?


q = deque()
q.append(group)
visited[group[0]][group[1]] = True

if group[0] == group[1] == group[2] :
    print(1)
    exit(0)


while q:
    cur_group = q.popleft()
    group_idx_comb = [(0,1), (0,2), (1,2)]

    
    for g in group_idx_comb:

        # 두 조합이 같다면 패스
        if cur_group[g[0]] == cur_group[g[1]]:
            continue

        new_group = copy.deepcopy(cur_group)

        # 큰쪽 작은쪽 비교
        if cur_group[g[0]] < cur_group[g[1]]:

            new_group[g[1]] = new_group[g[1]] - new_group[g[0]]
            new_group[g[0]] = new_group[g[0]]*2
        else:

            new_group[g[0]] = new_group[g[0]] - new_group[g[1]]
            new_group[g[1]] = new_group[g[1]]*2
        
        if visited[new_group[0]][new_group[1]] == True:
            continue
        
    
        # 세그룹이 모두 같다면
        if new_group[0] == new_group[1] == new_group[2]:
            print(1)
            exit(0)

        q.append(new_group)
        visited[new_group[0]][new_group[1]] = True

print(0)

deepcopy가 문제가 될것이라 생각해서 

구조를 조금 바꿔서 deepcopy를 안쓰는 방향으로 코드를 구성하였다

 

group_idx_comb 배열

해당 배열 0번째와 1번째에는 X, Y를 나타내고 2번째에는 X,Y에 해당되지 않는 idx를 나타내주었다

추후 새로운 리스트를 만들어서 큐에 넣어줄 때 필요하다

 

여기서 2번째 element가 deep copy를 안쓰기 위해 넣어준 것이다

 

import itertools
import copy
from collections import deque


group = list(map(int, input().split()))

visited = [[False]*(1501) for _ in range(1501)]

# dfs로 진행하면 안될 놈에게 계속 하게되는 함정이 있다


# 돌 그룹 개수가 같아지지 않다는 것을 알려면 어케?
    # --> 다시 원래 group으로 돌아온다? 아님 큐가 0가 된다?


q = deque()
q.append(group)
visited[group[0]][group[1]] = True

if group[0] == group[1] == group[2] :
    print(1)
    exit(0)


while q:
    cur_group = q.popleft()
    group_idx_comb = [(0,1,2), (0,2,1), (1,2,0)]

    
    for g in group_idx_comb:

        # 두 조합이 같다면 패스
        if cur_group[g[0]] == cur_group[g[1]]:
            continue

        new_group = [0]*3

        # 큰쪽 작은쪽 비교
        if cur_group[g[0]] < cur_group[g[1]]:
            new_group[g[1]] = cur_group[g[1]] - cur_group[g[0]]
            new_group[g[0]] = cur_group[g[0]]*2
            new_group[g[2]] = cur_group[g[2]]
        else:
            new_group[g[0]] = cur_group[g[0]] - cur_group[g[1]]
            new_group[g[1]] = cur_group[g[1]]*2
            new_group[g[2]] = cur_group[g[2]]
        
        if visited[new_group[0]][new_group[1]] == True:
            continue
 

        # 세그룹이 모두 같다면
        if new_group[0] == new_group[1] == new_group[2]:
            print(1)
            exit(0)

        q.append(new_group)
        visited[new_group[0]][new_group[1]] = True

print(0)

함수모양의 BFS로 한번더 리펙토링 해보았다

from collections import deque

group = list(map(int, input().split()))

s = sum(group)

visited = [[False]*(1501) for _ in range(1501)]

group_idx_comb = [(0, 1, 2), (0, 2, 1), (1, 2, 0)]

def bfs(a, b, c):
    q = deque()
    q.append((a, b, c))
    visited[a][b] = True
    
    while q:
        cur = q.popleft()

        if cur[0] == cur[1] == cur[2]:
            print(1)
            return

        for g in group_idx_comb:
            new_group = [0]*3
            if cur[g[0]] == cur[g[1]]:
                continue
            elif cur[g[0]] < cur[g[1]]:
                new_group[g[1]] = cur[g[1]] - cur[g[0]]
                new_group[g[0]] = cur[g[0]]*2
                new_group[g[2]] = cur[g[2]]
            else:
                new_group[g[0]] = cur[g[0]] - cur[g[1]]
                new_group[g[1]] = cur[g[1]]*2
                new_group[g[2]] = cur[g[2]]

            if visited[new_group[0]][new_group[1]] == True:
                continue

            q.append(new_group)
            visited[new_group[0]][new_group[1]] = True

    print(0)


bfs(group[0], group[1], group[2])

 

다른 분들 풀이를 보니 아예 위치 상관을 안하고 Sum을 기준으로 푸는 분들도 있었다

그분들 풀이를 좀더 보면서 이 문제는 보충해나갈 예정이다

속도차가 생각보다 있더라