2251번: 물통

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

풀이

package graph_search;

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

public class Main_2251_dfs {

    private static int[] maxVolume = new int[3];
    private static boolean[][][] visited = new boolean[201][201][201];
    private static List<Integer> result = new ArrayList<>();

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < 3; i++) {
            maxVolume[i] = Integer.parseInt(st.nextToken());
        }
    }

    private static void process() {
        dfs(0, 0, maxVolume[2]);
    }

    private static void dfs(int a, int b, int c) {
        visited[a][b][c] = true;

        if (a == 0) {
            result.add(c);
        }

        for (int departure = 0; departure < 3; departure++) {
            for (int destination = 0; destination < 3; destination++) {
                // 기존 a,b,c의 값을 유지해야 하므로 새로운 배열 생성하여 사용
                int[] newStatus = {a, b, c};

                if (departure == destination) {
                    continue;
                }

                if (newStatus[departure] == 0) {
                    continue;
                }

                pourWater(departure, destination, newStatus);

                if (visited[newStatus[0]][newStatus[1]][newStatus[2]] == false) {
                    dfs(newStatus[0], newStatus[1], newStatus[2]);
                }
            }
        }
    }

    private static void pourWater(int departure, int destination, int[] newStatus) {
        if (newStatus[departure] + newStatus[destination] < maxVolume[destination]) {
            newStatus[destination] = newStatus[departure] + newStatus[destination];
            newStatus[departure] = 0;
        } else {
            newStatus[departure] -= maxVolume[destination] - newStatus[destination];
            newStatus[destination] = maxVolume[destination];
        }
    }

    private static void output() {
        Collections.sort(result);

        int size = result.size();

        for (int i = 0; i < size; i++) {
            System.out.print(result.get(i) + " ");
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }
}

• 물통이 변할 수 있는 상태를 구하는 부분(2중 for문)에서 기존의 값(a,b,c)를 그대로 사용하여 제대로 작동하지 않는 문제가 있었음
  • newStatus 배열을 생성하고 그 값으로 재귀함수를 돌리는 것으로 문제를 해결함..
  • 객체의 불변성이 중요함을 깨달음