[Do It! 코딩테스트 자바편(김종관)] 문제 049(백준 2251번)

난이도

교재 설명 없이는 전혀 못 풀었을 문제. 처음에 교재 1~2단계 설명만 보고 풀려고 했지만, 코드가 너무 산으로 가서 교재 정답을 보았다. 그렇게 까지 코드가 이해하기 어려운 것은 아니지만, 아이디어와 구현도 코드가 나름 길다 보니 약간 헷갈렸다.

문제

물통 (백준: 2251번)

풀이

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[] capacity = new int[3];
    static int[] sender = { 0, 0, 1, 1, 2, 2 };
    static int[] receiver = { 1, 2, 0, 2, 0, 1 };
    static boolean[][] visited = new boolean[201][201];
    static ArrayList<Integer> answer = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 3; i++) {
            capacity[i] = sc.nextInt();
        }

        // 되는 경우를 탐색하면서 그래프 그리기
        bfs();

        // 정답 출력
        Collections.sort(answer);
        for (int i = 0; i < answer.size(); i++) {
            System.out.print(answer.get(i) + " ");
        }
        sc.close();
    }

    private static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        int[] start = { 0, 0 };
        queue.add(start);
        visited[0][0] = true;
        answer.add(capacity[2]);

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int aLiter = now[0];
            int bLiter = now[1];
            int cLiter = capacity[2] - aLiter - bLiter;

            for (int i = 0; i < 6; i++) {
                int[] next = { aLiter, bLiter, cLiter };

                // 물 옮기기
                next[receiver[i]] += next[sender[i]];
                next[sender[i]] = 0;
                if (next[receiver[i]] > capacity[receiver[i]]) {
                    next[sender[i]] = next[receiver[i]] - capacity[receiver[i]];
                    next[receiver[i]] = capacity[receiver[i]];
                }

                // 큐에 넣기
                if (!visited[next[0]][next[1]]) {
                    queue.add(next);
                    visited[next[0]][next[1]] = true;
                    if (next[0] == 0) {
                        answer.add(next[2]);
                    }
                }
            }
        }
    }
}