[파이썬] 백준 2251: 물통 (골드5)

[파이썬] 백준 2251: 물통 (골드5)

2251번: 물통

---

문제

---

풀이

 

0. 방향성 생각

• 물통에 담긴 물의 양을 튜플로 저장해서 visit set에 저장한다.
• BFS로 현재 물통에서 옮길 수 있는 방법 모두 탐색
• visit에 저장된 case중 A=0인 C를 answer set에 저장하고 출력

1. 입력

from collections import deque

size = list(map(int,input().split()))
init = (0,0,size[-1])
visit = {init}

• 초기 상태를 init으로 놓고 visit에 저장

2. BFS

q = deque([list(init)])
while q:
    state = q.popleft()

    if tuple(state) not in visit:
        continue

    for x in range(3):

        diff = size[x] - state[x]
        if diff:

            for nx in range(3):
                temp = state[:]

                if x != nx:
                    if diff < state[nx]:
                        temp[x] += diff
                        temp[nx] -= diff
                    else:
                        temp[x] += temp[nx] 
                        temp[nx] = 0

                    if tuple(temp) not in visit:
                        visit.add(tuple(temp))
                        q.append(temp)

• BFS로 탐색
• state에 저장된 물의 양이 visit에 없는 상태라면 탐색 시작
• 물병 x에 대해서 남은 공간 diff가 있으면 탐색 시작
• state를 복사한 temp을 변화시킨다
• 옆 물통 양 state[nx]가 남은 공간 diff 보다 적다면 현재 물통은 + diff, 옆 물통은 -diff
• 옆 물통 양 state[nx]가 남은 공간 diff보다 크거나 같다면 현재 물통은 전부 받고, 옆 물통은 0으로

3. 출력

answer = list({c for a,b,c in visit if not a})
answer.sort()
print(*answer)

• 해시 - > 리스트 -> 정렬 후 언패킹 출력

 

---

전체코드

from collections import deque

size = list(map(int,input().split()))
init = (0,0,size[-1])
visit = {init}

q = deque([list(init)])
while q:
    state = q.popleft()

    if tuple(state) not in visit:
        continue

    for x in range(3):

        diff = size[x] - state[x]
        if diff:

            for nx in range(3):
                temp = state[:]

                if x != nx:
                    if diff < state[nx]:
                        temp[x] += diff
                        temp[nx] -= diff
                    else:
                        temp[x] += temp[nx] 
                        temp[nx] = 0

                    if tuple(temp) not in visit:
                        visit.add(tuple(temp))
                        q.append(temp)

answer = list({c for a,b,c in visit if not a})
answer.sort()
print(*answer)

 

코멘트

.