[Java] 2251번. 물통 (#BFS)

1. 문항출처 : https://www.acmicpc.net/problem/2251

2. 문제해석

맨 처음 C 물통에서 A 혹은 B 물통으로 물을 옮기기 시작해서
물 옮기는 과정을 반복할 때
A 물통이 비어있을 때 C 물통에 담겨있는 물의 양으로 가능한 경우를 모두 출력해야한다.
따라서 각 과정마다 각 물통의 양을 가지고 너비우선탐색으로 모든 경우를 탐색한다.

3. 해결코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static int A, B, C;
    static int[] maxCapacity; // 각 물통의 최대 수용량
    static boolean[][] isVisited; // 물통의 상태를 탐색했었는지 여부
    static boolean[] availableCapicity; // C 물통의 가능한 수용량(정답)

    private void solution() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        maxCapacity = new int[]{A, B, C};
        isVisited = new boolean[A + 1][B + 1];
        availableCapicity = new boolean[C + 1];
        bfs();
        for (int i = 0; i < availableCapicity.length; i++) {
            if (availableCapicity[i]) sb.append(i).append(" ");
        }
        System.out.println(sb);
    }
    
	// 너비우선탐색
    void bfs() {
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{0, 0, C}); // 초기값
        while (!que.isEmpty()) {
            int[] status = que.poll();
            isVisited[status[0]][status[1]] = true; // 물통들의 현재상태 방문 체크
            
            // A 물통이 비어있는 상태이면 C 물통의 수용량이 정답이므로 체크
            if (status[0] == 0) availableCapicity[status[2]] = true;
            
            // 현재 상태에서 물을 옮길 수 있는 모든 경우에 대해서 다음 진행
            for (int i = 0; i < 3; i++) { // 물을 주는 물통번호
                for (int j = 0; j < 3; j++) { // 물을 받는 물통번호
                    if (i == j) continue; // 같은 물통이면 넘어가기
                    int[] newStatus = watering(status, i, j); // 물을 옮겼을 때의 새로운 상태
                    // 물을 옮길 수 있고, 방문한 적이 없는 상태면 que에 추가
                    if (newStatus != null && !isVisited[newStatus[0]][newStatus[1]]) {
                        que.add(newStatus);
                    }
                }
            }

        }
    }

	// 물을 옮기는 함수(현재 상태, 주는 물통번호, 받는 물통번호)
    int[] watering(int[] status, int sender, int receiver) {
    	//받는 물통에서 최대로 받을 수 있는 물의 양
        int residue = maxCapacity[receiver] - status[receiver];
        
        // 물을 받을 수 없거나, 물을 줄 수 없으면 null 값 반환
        if (residue == 0 || status[sender] == 0) return null;
        
        // 물 옮기기
        int[] newStatus = status.clone();
        if (residue < newStatus[sender]) {
            newStatus[sender] -= residue;
            newStatus[receiver] += residue;
        } else {
            newStatus[receiver] += newStatus[sender];
            newStatus[sender] = 0;
        }
        
        // 새로운 물통 상태 반환
        return newStatus;
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

}