[백준] 물통 - Java

문제 출처

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

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

 

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력 1 복사

8 9 10

예제 출력 1 복사

1 2 8 9 10

풀이 방법

• dfs를 활용해서 풀이하였다.
• 물통을 가득 채우거나, 비우거나 둘 중 하나를 택할 수 있으므로, 한 물통에서 다른 물통으로 물을 따라 낼 때에 넘치는지, 안넘치는지 여부만 판단하고 dfs를 수행한다.
  • 이때 a가 0이되는 부분을 캐치하여 set에 저장하고, 나중에 올림차순으로 정렬해준다.
• 물통을 옮길 수 있는 경우의 수는  A 에서 B, C로, B 에서 A, C로, C에서 A, B로 옮기는 총 6가지이므로
  • 넘치는지, 안넘치는지까지 해서 총 12개의 if 구문으로 dfs를 완성하면 끝

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static int A, B, C;
    static int[][][] visited;
    static Set<Integer> set = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 각 물통의 용량
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        visited = new int[A + 1][B + 1][C + 1];

        //물통을 옮길 수 있는 경우의 수
        //A -> B , A -> C, B -> A, B -> C, C -> A, C -> B 총 6가지
        dfs(0, 0, C);
        List<Integer> result = new ArrayList<>(set);
        Collections.sort(result);

        for(int r : result){
            System.out.print(r + " ");
        }       
    }

    public static void dfs(int a, int b, int c){
        if(visited[a][b][c] == 1){
            return;
        }

        visited[a][b][c] = 1;
        if(a == 0){
            set.add(c);
        }

        //6가지 경우의 수 적용
        //1. a -> b
        if(a + b > B){
            dfs(a + b - B, B, c);
        }
        else {
            dfs(0, a + b, c);
        }

        //2. a -> c
        if (a + c > C){
            dfs(a + c - C, b, C);
        }
        else {
            dfs(0, b, a + c);
        }

        //3. b -> a
        if(b + a > A){
            dfs(A, b + a - A, c);
        }
        else {
            dfs(b + a, 0, c);
        }

        //4. b -> c
        if(b + c > C){
            dfs(a, b + c - C, C);
        }
        else {
            dfs(a, 0, b + c);
        }

        //5. c -> a
        if(c + a > A){
            dfs(A, b, c + a - A);
        }
        else {
            dfs(a + c, b, 0);
        }

        //6. c -> b
        if(c + b > B){
            dfs(a, B, c + b - B);
        }
        else {
            dfs(a, b + c, 0);
        }
    }
}

결과

회고

• 처음 문제 볼때만해도 이게 왜 그래프 탐색인가 했다.