[Python][백준 2251] 물통

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

2251번: 물통

---

/*
신경써야 할 부분은 바로 :
1. 수통의 최대용량, 수통의 현재 채워진 용량 둘을 구분지어 활용
2. 물을 옮길때 수통이 가득차거나 빌 때까지 옮긴다
3. 도달했던 값은 방문처리로 재방문 방지
4. 결과값들을 정렬 후 출력

문제가 그리 어려워 보이진 않았지만 막상 풀려고 하니 멍해졌다
직접 얼마만큼의 물을 옮겨야 할지 먼저 계산해볼까 했지만 답이 없어보여서
그냥 두 가정 모두 실행해보고 수통의 물이 0보다 작거나 넘치면 리턴하는 식으로 설계했다
직관적으로 짜려고 했더니 dfs 를 12개나 써버렸다. 좀 더 잘 짠 사람의 코드가 궁금하다.
*/

---

import sys
input = sys.stdin.readline
 
def dfs(va,vb,vc) :
    # 오류값 확인 및 이미 방문한 경우 리턴
    if sum([va,vb,vc]) != c or (va,vb,vc) in check or va > a or vb > b or vc > c or va < 0 or vb < 0 or vc < 0:
        return
        
    if va == 0 and vc not in result :
        result.append(vc)
        
    check.append((va,vb,vc))
    
    # 물통이 바닥날 때까지 붓는 경우
    dfs(0,vb + va ,vc)
    dfs(0,vb ,vc+ va)
    dfs(va + vb,0,vc)
    dfs(va,0 ,vc+ vb)
    dfs(va,vb + vc,0)
    dfs(va + vc,vb ,0)
    
    # 물통이 가득찰 때까지 붓는 경우
    dfs(va - (b - vb),b,vc)
    dfs(va- (c - vc),vb,c)
    dfs(a,vb- (a - va),vc)
    dfs(va,vb- (c - vc),c)
    dfs(a,vb,vc- (a - va))
    dfs(va,b,vc- (b - vb))
 
a,b,c = map(int ,input().split())
vA,vB,vC = (0,0,c)
result = []
check = []

dfs(vA,vB,vC)

print(" ".join(list(map(str, sorted(result)))))

---

풀 때 어려웠던 점 또는 느낀점 :

공익 2일차 문제풀기 성공

매일 이렇게 풀면 소집해제까지 600개가 넘는 문제를 풀 수 있다.

소집해제 하면 PS 고수가 되어있을수도..? ㅎㅎ

 

문제를 다시 풀기 시작한지 얼마 안되어서 그런지

뇌가 아직 굳어있는게 느껴졌다. 그래도 어제보단 할만했다.

내일은 오늘보다 잘해야겠다.

---

참고할만한 다른 사람 코드 :

from collections import deque


def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = 1
        q.append((x, y))


def bfs():
    q.append((0,0))  # 처음 물통 a,b는 0,0
    visited[0][0] = 1
    while q:
        x, y = q.popleft()
        z = c - x - y  # z는 a와b에 의해 결정된다.
        if x == 0:  # 조건에서 a물통이 0일때 이므로
            answer.append(z)

        # a에서 b 물을 옮기는 경우
        if x > 0 and y < b:  # a에 물이 있고 b에 물이 가득차있지 않을 때
            w = min(x, b - y)
            pour(x - w, y + w)
        # a에서 c
        if x > 0 and z < c:
            w = min(x, c - z)
            pour(x - w, y)

        # b에서 a
        if y > 0 and x < a:
            w = min(y, a - x)
            pour(x + w, y - w)
        # b에서 c
        if y > 0 and z < c:
            w = min(y, c - z)
            pour(x, y - w)

        # c에서 a
        if z > 0 and x < a:
            w = min(z, a - x)
            pour(x + w, y)
        # c에서 b
        if z > 0 and y < b:
            w = min(z, b - y)
            pour(x, y + w)


if __name__ == "__main__":
    a, b, c = map(int, input().split())
    # visited: a 물통과 b 물통의 양에 따라 c 물통의 양이 정해지기 때문에
    # a,b 두 통을 실행한 적이 있는지 확인하는 2중리스트
    visited = [[0] * (b + 1) for _ in range(a + 1)]
    # 답을 넣을 배열
    answer = []
    # BFS
    q = deque()
    bfs()
    # 답 출력
    answer.sort()
    print(' '.join(list(map(str, answer))))
    
    // 출처 : https://deok2kim.tistory.com/81

 

다른 사람들도 비슷하게 푼듯 하다 

내거보다 가독성이 좋고 나는 가득차거나 빌 때를 그냥 다 넣고 조건문으로 걸렀지만

위의 코드는 미리 min 함수를 통해 둘 중에 하나만 선택했다.

함수 사용을 줄일 수 있어 좋아보인다. 

또한 변수를 두개만 사용하는건 신기하다.