[백준/bfs] 2251번: 물통

-문제:https://www.acmicpc.net/problem/2251

 

bfs를 그래프나 행렬로만 접했어서 어떻게 접근해야할지 잘 몰랐던 문제다. 

찾아보니 물통의 크기에 따라 따를 수 있는 모든 경우의 수를 구하는 것을 bfs로 진행해야한다고 한다

a,b,c에 담겨있는 물의 양을 x,y,z라고 한다면 

 

x를 b에 담을 때 두 가지의 경우가 있다. 

1. x를 모두 b에 담는경우(x가 b-y보다 더 작다면 x를 모두 b에 부을 수 있다 )

2. b가 꽉 차는 경우(만약 b-y(b에 남은 공간)가 x보다 작으면 x를 다 따르지 못하고 b만 꽉 찬다)

=> water=min(x,b-y)

위와 같은 방식으로 x를 기준으로,y를 기준으로,z를 기준으로 if문을 작성한 후 pour를 해주면 된다 

x&(b,y), x&(c,z), y&(a,x), y&(c,z), z&(a,x), z&(b,y) 총 여섯가지의 if문이 생성된다 

 

if문을 다 작성한 뒤 pour에 파라미터를 넣을 때 조심해야한다. pour에 들어가는 파라미터는 a의 용량 변화한거와 b의 용량 변화한거를 넣어야한다 

 

 

-정답풀이:

from collections import deque

#x는 a에 담긴 물의 양,y는 b에 담긴 물의 양
def pour(x,y):
    if not visit[x][y]:
        visit[x][y]=1
        queue.append([x,y])
        
def bfs():
    queue=deque()
    queue.append((0,0))
    visit[0][0]=1
    while queue:
        x,y=queue.popleft()
        z=c-x-y #처음에 c에만 물이 있었으므로 x,y값 빼면 c에 담긴 물의 양 
        
        #문제에서 주어진 조건이 첫 번재 물통이 비어 있을 때, 세 번째 물통에 담겨있을 수 있는 물의 양 구하는 것임
        if x==0:
            ans.append(z)
            
        if x>0 and b>y:
            water=min(x,b-y)
            #A에서 B로 물 이동(B 꽉 채움)
            pour(x-water,y+water)
        if x>0 and c>z:
            water=min(x,c-z)
            #A에서 C로 물 이동(C 꽉 채움)
            pour(x-water,y) #b에서의 변화는 없으므로
            
        if y>0 and a>x:
            water=min(y,a-x)
            #B에서 A로 물 이동(A 꽉채움)
            pour(x+water,y-water)
        if y>0 and c>z:
            water=min(y,c-z)
            #B에서 C로 물 이동(C 꽉채움)
            pour(x,y-water)
            
        if z>0 and a>x:
            water=min(z,a-x)
            #C에서 A로 물 이동(A 꽉 채움)
            pour(x+water,y)
        if z>0 and b>y:
            water=min(z,b-y)
            #C에서 B로 물 이동(B 꽉 채움)
            pour(x,y+water)
            
a,b,c=map(int,input().split())
ans=[]
visit=[[0]*(b+1) for _ in range(a+1)]

bfs()

ans.sort()
for i in ans :
    print(i,end=' ')

 

풀면서 범했던 실수들

1) 띄어쓰기 오류(Indentation오류)

2)오타: for i in range ans: -> for i in ans:

3)출력할 때 숫자 간 간격 띄우기(문제 출력 조건 만족하게 작성하기): print(i,end='') ->print(i,end=' ') 

4)queue에 (0,0) 두번 삽입,,,