[백준/Swift] 2251 : 물통

 

 

• BOJ_2251.swift

• 2251 : 물통/ 문제 소개                            
• 풀이 과정
• 코드 구현

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

2251번: 물통

2251 : 물통 / 문제 소개

 

부피가 A B C (1<= A,B,C <= 200 ) 리터인 세개의 물통이 있다.

처음에는 C 물통에만 가득 차 있다.

이제 다른 물통들로 쏟아 부울 수 있는데 조건이 있다.

한 물통이 비거나 or 다른 한 물통이 가득 찰 때 까지 물을 쏟아 부울 수 있다.

 

A물통이 비어있을 때 C물통에 담길 수 있는 물의 양을 모두 구해내시오!!

풀이 과정

 

물통은 전부 3개다.

한개의 물통에 대해서 서로 다른 두개의 물통에 동시에 부울 수 없다. 물을 붓는 물통이 비거나, 부어짐을 당하는 물통이 가득 찰 때 까지 물을 붓기 때문이다.

 

그렇다면 각각의 물통에 대해서 다른 물통으로 부울 수 있는 경우의 수는

A 물통에서 B물통으로

A 물통에서 C물통으로

B 물통에서 A물통으로

B 물통에서 C물통으로

C 물통에서 A물통으로

C 물통에서 B물통으로 

6가지 서로 다른 경우의 수를 통해 각각의 물통에서 물을 부울 수 있다.

 

예를들어 

input 

 8 9 10

일때 물통의 크기는 maxA = 8 , maxB = 9, maxC = 10으로 정할 수 있다.

초기 물통에 들어있는 물 양은

A B C

0 0 10이다.

 

이 경우에서 물을 붓는 경우는

0 9 1

8 0 2 두개가 나온다.

 

첫번째 (0 9 1)의 경우  초기값 0 0 10일 때 C에서 B로 물을 붓는 방법은

B = maxB , C = ( b + c )  - maxC로 구할 수 있다.

 

그렇다면

A B C

8 0 2의 경우에서 C에서 B로 물을 붓는 방법은 위에서 구한 식을 이용해

B = maxB, C = ( b + c ) - maxC 로 계산이 될 까?

그렇지 않다.

이 경우는 C에서 B로 물을 부울 수 있는데 C의 양이 B의 양보다 크지 않음으로 B는 가득 찰 수 없다. 

B = b + c, C = 0 이렇게 계산해주어야 한다.

C에서 B로 물을 부을 때 C와 B에 들어있는 물통의 양에 따라서 C, B의 부피가 계산된다는 것이다.

 

이렇게 경우를 따지면 6 * 2 == 12개의 경우의 수가 나온다.

 

이렇게 특정 조건에 따라 물의 높이가 다른 3개의 물통이 존재하는데 반복해서 구해질 수 있음으로

visited를 통해 방문 체크를 한다.

또한 새로 구한 물통의 물 높이에서 다른 물통으로 물을 부울 수 있기에 queue에 추가를 해가면서 구하면 된다.

그리고 A == 0일 때 C의 물 높이를 정답 배열에 저장해나가서 소팅 후 답을 출력하면 된다!

코드 구현

 

import Foundation

func BFS(_ ABC : [Int])
{
    let maxA    = ABC[0] , maxB = ABC[1] , maxC = ABC[2]
    var queue   = [(0,0,maxC)]
    var index   = 0
    var res     = ""
    var ans     = [Int]()
    var visited = Array(repeating: Array(repeating: Array(repeating: false,count:ABC[2] + 1), count :ABC[1] + 1) , count: ABC[0] + 1)
    visited[0][0][maxC] = true
    
    while queue.count != index
    {
        let (curA,curB,curC) = queue[index]
        index += 1
        if curA == 0
        {
            ans.append(curC)
        }
        // C에서 B에 물을 채우는 경우 . a 는 상관x
        if (curB + curC) > maxB && !visited[curA][maxB][(curB+curC)-maxB]
        {
            visited[curA][maxB][(curB+curC)-maxB] = true
            queue.append((curA,maxB,(curB+curC)-maxB))
        }
        else if curB + curC <= maxB
        {
            if !visited[curA][curB+curC][0]
            {
                visited[curA][curB+curC][0] = true
                queue.append((curA,curB+curC,0))
            }
        }
        // C에서 A에 물을 채우는 경우. B는 상관 x
        if (curA + curC) > maxA && !visited[maxA][curB][(curA+curC) - maxA]
        {
            visited[maxA][curB][(curA+curC)-maxA] = true
            queue.append((maxA,curB,(curA+curC)-maxA))
        }
        else if curA+curC <= maxA
        {
             if !visited[curA+curC][curB][0]
            {
                 visited[curA+curC][curB][0] = true
                 queue.append((curA+curC,curB,0))
            }
        }
        // B에서 A에 물을 채우는 경우. C는 상관 x
        if (curB + curA) > maxA && !visited[maxA][(curB + curA) - maxA][curC]
        {
            visited[maxA][(curB+curA)-maxA][curC] = true
            queue.append((maxA,(curB+curA)-maxA,curC))
        }
        else if curB+curA <= maxA
        {
            if !visited[curA+curB][0][curC]{
                visited[curA+curB][0][curC] = true
                queue.append((curA+curB,0,curC))
            }
        }
        //B에서 C에 물을 채우는 경우. A는 상관x
        if (curB + curC) > maxC && !visited[curA][(curB+curC)-maxC][maxC]
        {
            visited[curA][(curB+curC)-maxC][maxC] = true
            queue.append((curA,(curB+curC)-maxC,maxC))
        }
        else if curB+curB <= maxC
        {
            if !visited[curA][0][curB+curC]
            {
                visited[curA][0][curB+curC] = true
                queue.append((curA,0,curB+curC))
            }
        }
        // A에서 B에 물을 채우는 경우. C는 상관x
        if (curA + curB) > maxB && !visited[(curA+curB)-maxB][maxB][curC]
        {
            visited[(curA+curB)-maxB][maxB][curC] = true
            queue.append(((curA+curB)-maxB,maxB,curC))
        }else if curA + curB <= maxB
        {
            if !visited[0][curA+curB][curC]
            {
                visited[0][curA+curB][curC] = true
                queue.append((0,curA+curB,curC))
            }
        }
        // A에서 C에 물을 채우는 경우. B는 상관x
        if (curA + curC) > maxC && !visited[(curA+curC)-maxC][curB][maxC]
        {
            visited[(curA+curC)-maxC][curB][maxC] = true
            queue.append(((curA+curC)-maxC,curB,maxC))
        }
        else if curA+curC <= maxC
        {
            if !visited[0][curB][curA+curC]
            {
                visited[0][curB][curA+curC] = true
                queue.append((0,curB,curA+curC))
            }
        }
    }
    ans.sort()
    ans.forEach
    {
        res += "\($0) "
    }
    print(res)
}
func BOJ_2251()
{
    var ABC   = readLine()!.split(separator: " ").map{Int(String($0))!}
    BFS(ABC)
}
BOJ_2251()

 

visit my github