[백준] 2251번 물통 - Java

문제

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

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

입력

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

출력

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

알고리즘: BFS

풀이

간단한 BFS 문제이다. 근데 구현이 조금 난이도 있는 편이다.

A, B, C의 범위가 (1<=A,B,C<=200)이기 때문에 방문 체크를 위한 3차원 배열이 필요하다.
그리고 방문할 수 있는 좌표는 약 200 200 200이므로 충분히 BFS 풀이가 가능하다.

현재 좌표에서 방문 체크를 할 수 있는 좌표는 총 6가지이다.

1. A가 B에 물을 붓는 경우
2. A가 C에 물을 붓는 경우
3. B가 A에 물을 붓는 경우
4. B가 C에 물을 붓는 경우
5. C가 A에 물을 붓는 경우
6. C가 B에 물을 붓는 경우

이 6가지 새로운 좌표를 방문할 수 있는지 체크하고 방문할 수 있다면 que에 넣고 너비 우선 탐색을 진행하면 된다.

소스 코드

import java.io.*;
import java.util.*;

class Node {
    int a,b,c;
    Node(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

public class Main {
    static int volume[] = new int[3]; //0 -> A, 1 -> B, 2 -> C
    static boolean c_visited[] = new boolean[201];
    static boolean visited[][][] = new boolean[201][201][201];
    static ArrayList<Integer> ans_list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        volume[0] = Integer.parseInt(st.nextToken());
        volume[1] = Integer.parseInt(st.nextToken());
        volume[2] = Integer.parseInt(st.nextToken());
        BFS();
        Collections.sort(ans_list);
        for(int i=0; i<ans_list.size(); i++) {
            sb.append(ans_list.get(i) + " ");
        }
        System.out.println(sb.toString().trim());
    }
    
    static void BFS() {
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(0, 0, volume[2])); 
        visited[0][0][volume[2]] = true;
        while(que.size()!=0) {
            Node n = que.poll();
            if(n.a==0) {
                if(!c_visited[n.c]) {
                    ans_list.add(n.c);
                    c_visited[n.c] = true;
                }
            }
            if(n.a!=0) {
                for(int i=0; i<2; i++) {
                    Node new_n;
                    if(i==0) new_n = pour_water(n, 0, 1);
                    else new_n = pour_water(n, 0, 2);
                    //방문 검사
                    if(!visited[new_n.a][new_n.b][new_n.c]) {
                        que.add(new_n);
                        visited[new_n.a][new_n.b][new_n.c] = true;
                    }
                }
            }
            if(n.b!=0) {
                for(int i=0; i<2; i++) {
                    Node new_n;
                    if(i==0) new_n = pour_water(n, 1, 0);
                    else new_n = pour_water(n, 1, 2);
                    //방문 검사
                    if(!visited[new_n.a][new_n.b][new_n.c]) {
                        que.add(new_n);
                        visited[new_n.a][new_n.b][new_n.c] = true;
                    }
                }
            }
            if(n.c!=0) {
                for(int i=0; i<2; i++) {
                    Node new_n;
                    if(i==0) new_n = pour_water(n, 2, 0);
                    else new_n = pour_water(n, 2, 1);
                    //방문 검사
                    if(!visited[new_n.a][new_n.b][new_n.c]) {
                        que.add(new_n);
                        visited[new_n.a][new_n.b][new_n.c] = true;
                    }
                }
            }
        }
    }
    
    static Node pour_water(Node n, int from, int to) {
        int arr[] = {n.a, n.b, n.c};
        arr[to] += arr[from];
        arr[from] = 0;
        if(arr[to] > volume[to]) {
            arr[from] = arr[to] - volume[to];
            arr[to] = volume[to];
        }
        return new Node(arr[0], arr[1], arr[2]);
    }
}