[백준] 물통(2251)

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

이 문제는 그래프의 원리를 적용하여 그래프를 역으로 그리는 방식으로 접근해야하는 문제이다. A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 변경할 수 있는 무게 상태를 에지로 연결하여 인접하는 노드에 추가한다고 생각해야 한다.

처음에 물통 A, B는 비어 있고, C는 꽉 차있으므로 최초 출발 노드를 (0, 0, 3번째 물통의 용량)으로 초기화한다.

노드에서 갈 수 있는 모든 경우의 수에 대해 다음 노드를 정해 큐에 추가한다. 이 때, A, B, C 무게가 동일한 노드에 방문한 이력이 있는 경우 큐에 추가하지 않는다.

이동할 수 있는 모든 경우의 수는 다음과 같다.
A -> B, A -> C, B -> A, B -> C, C -> A, C -> B

이를 코드로 표현하면 다음과 같다.

// 물을 6가지 경우로 붓는 케이스를 표현하기 위한 배열
    static int[] Sender = {0, 0, 1, 1, 2, 2};
    static int[] Receiver = {1, 2, 0, 2, 0, 1};

A = 0, B = 1, C = 2로 대응시켰다.
따라서 Sender[0] -> Receiver[0]는 A -> B와 동일한 의미가 된다.

보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0으로 초기화한다. 만약 받는 물통이 넘치는 경우 초과하는 값만큼 보내는 물통에 남겨주어야 한다.

// 6가지 붓기 시도를 반복
for (int k = 0; k < 6; k++) {
	int[] next = {A, B, C};
    next[Receiver[k]] += next[Sender[k]];
    next[Sender[k]] = 0;

    // 물통의 용량이 초과하는 경우
    if (next[Receiver[k]] > now[Receiver[k]]) {
    	next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]]; // 초과하는 만큼 이전 물통에 넣어주고
        next[Receiver[k]] = now[Receiver[k]]; // 대상 물통은 최대치로 채움
	}
...

next 배열에는 A, B, C의 최대 용량이 들어있다. 따라서 next[Receiver[k]] += next[Sender[k]];는 Sender가 가진 물의 양을 Receiver에게 부어준 후, next[Sender[k]] = 0을 통해 Sender는 0으로 초기화시킨다.

만약 물통의 용량이 초과하는 경우 초과하는 만큼은 이전 물통에 넣어두고, 채워야 하는 물통은 최대치로 설정하는 것이다.

마지막으로 A, B의 물의 양을 이용하여 방문 배열을 체크하여 새로운 상태에서 A가 비어있다면 answer에 기록한다.

// A와 B의 물의 양을 이용해 방문 배열 체크
if (!visited[next[0]][next[1]]) {
	visited[next[0]][next[1]] = true;
    queue.add(new AB(next[0], next[1]));

    // 만약 새로운 상태에서 A가 비어있다면 answer 배열에 기록
    if (next[0] == 0) {
    	answer[next[2]] = true;
    }
}

따라서 전체 소스코드는 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P_2251 {
    // 물을 6가지 경우로 붓는 케이스를 표현하기 위한 배열
    static int[] Sender = {0, 0, 1, 1, 2, 2};
    static int[] Receiver = {1, 2, 0, 2, 0, 1};
    static boolean[][] visited; // 물통 A와 B에 담긴 물의 양의 방문 여부
    static boolean[] answer; // A가 비어있을 때 C에 담길 수 있는 물의 양
    static int[] now; // 각 물통의 최대 용량

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        now = new int[3];
        now[0] = sc.nextInt();
        now[1] = sc.nextInt();
        now[2] = sc.nextInt();

        visited = new boolean[201][201];
        answer = new boolean[201];

        BFS();

        for (int i = 0; i < answer.length; i++) {
            if (answer[i]) System.out.print(i + " ");
        }
    }

    public static void BFS() {
        Queue<AB> queue = new LinkedList<>();
        queue.add(new AB(0, 0));
        visited[0][0] = true;
        answer[now[2]] = true;

        while (!queue.isEmpty()) {
            AB p = queue.poll();
            int A = p.A;
            int B = p.B;
            int C = now[2] - A - B;

            // 6가지 붓기 시도를 반복
            for (int k = 0; k < 6; k++) {
                int[] next = {A, B, C};
                next[Receiver[k]] += next[Sender[k]];
                next[Sender[k]] = 0;

                // 물통의 용량이 초과하는 경우
                if (next[Receiver[k]] > now[Receiver[k]]) {
                    next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]]; // 초과하는 만큼 이전 물통에 넣어주고
                    next[Receiver[k]] = now[Receiver[k]]; // 대상 물통은 최대치로 채움
                }

                // A와 B의 물의 양을 이용해 방문 배열 체크
                if (!visited[next[0]][next[1]]) {
                    visited[next[0]][next[1]] = true;
                    queue.add(new AB(next[0], next[1]));

                    // 만약 새로운 상태에서 A가 비어있다면 answer 배열에 기록
                    if (next[0] == 0) {
                        answer[next[2]] = true;
                    }
                }
            }
        }
    }
}

class AB {
    int A;
    int B;

    public AB(int A, int B) {
        this.A = A;
        this.B = B;
    }
}

물통 C는 이미 문제에서 용량이 주어지므로, 방문 배열인 boolean[][] visited와 같이 2차원 배열로 선언하여 A와 B에 해당하는 물의 용량을 체크하는 것으로 새로운 상태를 확인할 수 있다는 점을 기억하자.