[백준 2251] 물통 - python (solved.ac - 실버 1)

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

2251번: 물통

풀이

문제를 보았을때 알수있는 힌트

ABC의 물통을 반복적으로 움직이면 될듯한 문제라고 생각이 들었다.

• A->B
• A->C
• B->A
• B->C
• C->A
• C->B

총 6개를 반복하면 A가 0일 때 C의 물의 양을 찾으면 된다.

 

하지만 언제 종료를 해야할지 감이 안와서 다른 사람들의 푼 풀이과정을 보며 힌트를 얻었다. 

방문했는지 확인하는 변수를 만들어서 이를 해결하는 것을 알수있었다.

방문 관련한 변수는 리스트 형식으로 [A][B]의 2차 배열 형식의 크기이다. 

예를 들어, A가 0이고 B가 0이면 방문 변수도 [0][0]를 True 처리하여 다시 안들려도 된다. 

 

BFS와 DFS 모두 다 풀리는문제이지만 나는 DFS를 통하여 풀었다.

import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    if visited[x][y]!=True:
        visited[x][y]=True
        z = c-x-y
        if x==0:
            result.append(z)
        #x-> y
        water = min(x, b-y)
        dfs(x-water,y+water)
        #x-> z
        water = min(x, c-z)
        dfs(x-water,y)
        #y-> x
        water = min(y, a-x)
        dfs(x+water,y-water)
        #y-> z
        water = min(y, c-z)
        dfs(x,y-water)
        #z-> x
        water = min(z, a-x)
        dfs(x+water,y)
        #z-> y
        water = min(z, b-y)
        dfs(x,y+water)

input= sys.stdin.readline

a,b,c = list(map(int,input().split()))

visited=[[False]*(b+1) for _ in range(a+1)]

result =[]

dfs(0,0)
result.sort()
print(*result)

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2251.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리