코테 노트/백준

백준 2251 물통 Python 3

화요밍 2021. 8. 20. 16:20
728x90
반응형

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

 

2251번: 물통

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부

www.acmicpc.net

 

최종 코드

 

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.

github.com

import sys
def dfs(a, b, c, visit):
    if a == 0:
        ans[c]+=1
    #물통 A에서 옮기는 경우
    if a > 0:
        #물통 B로 옮길 수 있는 경우
        if b < B:
            #물통 B의 남은 용량
            l = B-b
            #B가 가득찰 때까지 붓는다
            if a >= l:
                if not visit[a-l][B][c]:
                    visit[a-l][B][c] = 1
                    dfs(a-l, B, c, visit)
                    visit[a-l][B][c] = 0
            #A가 빌 때까지 붓는다
            elif not visit[0][b+a][c]:
                visit[0][b+a][c] = 1
                dfs(0, b+a, c, visit)
                visit[0][b+a][c] = 0
        #물통 C로 옮길 수 있는 경우
        if c < C:
            #물통 C의 남은 용량
            l = C-c
            #C가 가득찰 때까지 붓는다
            if a >= l:
                if not visit[a-l][b][C]:
                    visit[a-l][b][C] = 1
                    dfs(a-l, b, C, visit)
                    visit[a-l][b][C] = 0
            #A가 빌 때까지 붓는다
            elif not visit[0][b][c+a]:
                visit[0][b][c+a] = 1
                dfs(0, b, c+a, visit)
                visit[0][b][c+a] = 0
    #물통 B에서 옮기는 경우
    if b > 0:
        #물통 A로 옮길 수 있는 경우
        if a < A:
            #물통 A의 남은 용량
            l = A-a
            #A가 가득찰 때까지 붓는다
            if b >= l:
                if not visit[A][b-l][c]:
                    visit[A][b-l][c] = 1
                    dfs(A, b-l, c, visit)
                    visit[A][b-l][c] = 0
            #B가 빌 때까지 붓는다
            elif not visit[a+b][0][c]:
                visit[a+b][0][c] = 1
                dfs(a+b, 0, c, visit)
                visit[a+b][0][c] = 0
        #물통 C로 옮길 수 있는 경우
        if c < C:
            #물통 C의 남은 용량
            l = C-c
            #C가 가득찰 때까지 붓는다
            if b >= l:
                if not visit[a][b-l][C]:
                    visit[a][b-l][C] = 1
                    dfs(a, b-l, C, visit)
                    visit[a][b-l][C] = 0
            #B가 빌 때까지 붓는다
            elif not visit[a][0][c+b]:
                visit[a][0][c+b] = 1
                dfs(a, 0, c+b, visit)
                visit[a][0][c+b] = 0
    #물통 C에서 옮기는 경우
    if c > 0:
        #물통 A로 옮길 수 있는 경우
        if a < A:
            #물통 A의 남은 용량
            l = A-a
            #A가 가득찰 때까지 붓는다
            if c >= l:
                if not visit[A][b][c-l]:
                    visit[A][b][c-l] = 1
                    dfs(A, b, c-l, visit)
                    visit[A][b][c-l] = 0
            #C가 빌 때까지 붓는다
            elif not visit[a+c][b][0]:
                visit[a+c][b][0] = 1
                dfs(a+c, b, 0, visit)
                visit[a+c][b][0] = 0
        #물통 B로 옮길 수 있는 경우
        if b < B:
            #물통 B의 남은 용량
            l = B-b
            #B가 가득찰 때까지 붓는다
            if c >= l:
                if not visit[a][B][c-l]:
                    visit[a][B][c-l] = 1
                    dfs(a, B, c-l, visit)
                    visit[a][B][c-l] = 0
            #C가 빌 때까지 붓는다
            elif not visit[a][b+c][0]:
                visit[a][b+c][0] = 1
                dfs(a, b+c, 0, visit)
                visit[a][b+c][0] = 0

A, B, C = map(int, sys.stdin.readline().split())
ans = [0]*(C+1)
visit = [[[0]*201 for _ in range(201)] for _ in range(201)]
dfs(0, 0, C, visit)

for i in range(C+1):
    if ans[i] > 0: print(i, end=" ")

풀이 과정

풀이 시간 52분

import sys
def dfs(a, b, c, visit):
	#물통 A가 빈 경우, 물통 C 용량의 경우의 수를 카운팅
    if a == 0:
        ans[c]+=1
        
    #물통 A에서 옮기는 경우
    if a > 0:
        #물통 B로 옮길 수 있는 경우
        if b < B:
            #물통 B의 남은 용량
            l = B-b
            #B가 가득찰 때까지 붓는다
            if a >= l:
                if not visit[a-l][B][c]:
                    visit[a-l][B][c] = 1
                    dfs(a-l, B, c, visit)
                    visit[a-l][B][c] = 0
            #A가 빌 때까지 붓는다
            elif not visit[0][b+a][c]:
                visit[0][b+a][c] = 1
                dfs(0, b+a, c, visit)
                visit[0][b+a][c] = 0
                
        #물통 C로 옮길 수 있는 경우
        if c < C:
            #물통 C의 남은 용량
            l = C-c
            #C가 가득찰 때까지 붓는다
            if a >= l:
                if not visit[a-l][b][C]:
                    visit[a-l][b][C] = 1
                    dfs(a-l, b, C, visit)
                    visit[a-l][b][C] = 0
            #A가 빌 때까지 붓는다
            elif not visit[0][b][c+a]:
                visit[0][b][c+a] = 1
                dfs(0, b, c+a, visit)
                visit[0][b][c+a] = 0
                
    #물통 B에서 옮기는 경우
    if b > 0:
        #물통 A로 옮길 수 있는 경우
        if a < A:
            #물통 A의 남은 용량
            l = A-a
            #A가 가득찰 때까지 붓는다
            if b >= l:
                if not visit[A][b-l][c]:
                    visit[A][b-l][c] = 1
                    dfs(A, b-l, c, visit)
                    visit[A][b-l][c] = 0
            #B가 빌 때까지 붓는다
            elif not visit[a+b][0][c]:
                visit[a+b][0][c] = 1
                dfs(a+b, 0, c, visit)
                visit[a+b][0][c] = 0
                
        #물통 C로 옮길 수 있는 경우
        if c < C:
            #물통 C의 남은 용량
            l = C-c
            #C가 가득찰 때까지 붓는다
            if b >= l:
                if not visit[a][b-l][C]:
                    visit[a][b-l][C] = 1
                    dfs(a, b-l, C, visit)
                    visit[a][b-l][C] = 0
            #B가 빌 때까지 붓는다
            elif not visit[a][0][c+b]:
                visit[a][0][c+b] = 1
                dfs(a, 0, c+b, visit)
                visit[a][0][c+b] = 0
                
    #물통 C에서 옮기는 경우
    if c > 0:
        #물통 A로 옮길 수 있는 경우
        if a < A:
            #물통 A의 남은 용량
            l = A-a
            #A가 가득찰 때까지 붓는다
            if c >= l:
                if not visit[A][b][c-l]:
                    visit[A][b][c-l] = 1
                    dfs(A, b, c-l, visit)
                    visit[A][b][c-l] = 0
            #C가 빌 때까지 붓는다
            elif not visit[a+c][b][0]:
                visit[a+c][b][0] = 1
                dfs(a+c, b, 0, visit)
                visit[a+c][b][0] = 0
                
        #물통 B로 옮길 수 있는 경우
        if b < B:
            #물통 B의 남은 용량
            l = B-b
            #B가 가득찰 때까지 붓는다
            if c >= l:
                if not visit[a][B][c-l]:
                    visit[a][B][c-l] = 1
                    dfs(a, B, c-l, visit)
                    visit[a][B][c-l] = 0
            #C가 빌 때까지 붓는다
            elif not visit[a][b+c][0]:
                visit[a][b+c][0] = 1
                dfs(a, b+c, 0, visit)
                visit[a][b+c][0] = 0

A, B, C = map(int, sys.stdin.readline().split())

#물통 C의 가능한 용량의 경우의 수를 체크 -> 0~C리터 중에서 가능
ans = [0]*(C+1)

#물통 A, B, C의 용량의 경우의 수를 체크 -> visit[A][B][C]
visit = [[[0]*201 for _ in range(201)] for _ in range(201)]

#처음에 물통 A, B는 비어있고, C는 가득차있다
dfs(0, 0, C, visit)

for i in range(C+1):
    if ans[i] > 0: print(i, end=" ")
#시간복잡도 = O(V+E) = O(V), 공간복잡도 = O(V)
#최악의 경우 V = 200x200x200 = 6,000,000, E = 3x6,000,000 = 18,000,000 -> 24,000,000번의 연산 필요
#파이썬은 2000만 번의 연산에 1초가 소요된다

 

728x90
반응형

'코테 노트 > 백준' 카테고리의 다른 글

백준 3184 양 C++  (0) 2021.08.24
백준 2210 숫자판 점프 Python3  (0) 2021.08.22
백준 17779 게리맨더링 2 C++  (0) 2021.08.19
백준 16173 점프왕 쩰리 (Small) Python3  (0) 2021.08.19
백준 17142 연구소 3 C++  (0) 2021.08.18

'코테 노트/백준'의 다른글

  • 현재글백준 2251 물통 Python 3

관련글

댓글

티스토리툴바