[백준 2251] 물통 (JAVA)

백준 2251번 문제 - 물통

2251번: 물통

---

문제 분석

 

• 물은 C에만 가득찬 상태로 시작
• 물을 옮길 때 물을 받는 쪽이 가득차거나, 물을 주는 쪽이 비는 경우만 가능
• 이 과정을 실행해서 A가 비어있을 때 C의 담긴 물의 양의 경우의 수를 모두 출력
  • ex) 0 | 0 | 10 , 0 | 1 | 9 , 0 | 2 | 8 , 0 | 8 | 2 , 0 | 9 | 1
         ➡️ C의 경우의 수(오름차순) : 1, 2, 8, 9, 10

---

 

해결 키 포인트

 

• BFS(너비 우선 탐색) 개념 파악
• 문제 이해가 일단 어려웠음 → 그냥 쉽게 A 통은 빌 때 가능한 C의 경우의 수를 다 출력
• 어떻게 이들을 동적으로 실행할지에 대해 문제 해결이 어려웠음 (필자는 결국 스스로 풀기를 포기했다)
  나의 경험을 토대로 푸는데 도움이 될만한 힌트는 다음과 같다. 
  
  • 힌트 1) 가능한 물 움직임은 총 6가지이다 ( A→B, A→C, B→A, B→C, C→A, C→B)
  • 힌트 2) 일부 경우의 수만 확인해서는 답이 없다, 가능한 모든 경우의 수를 확인하는 방법을 택해라
                - A, B, C 모두 최대 201까지만 커질 수 있음, 각 수(A,B,C)가 0부터 201까지 모든 경우의 수를 확인
  • 힌트 3) 힌트 2에서 201을 A, B, C 다 확인하기보다 덜 복잡하게 A, B만 확인해도 된다
                 ( WHY? A, B로 C를 유추 할 수 있기 때문이다)
  • 힌트 4) 물을 sender에서 receiver로 따를 때, sender의 물 양이 receiver의 최대 물 양보다 많을 경우는 어떻게 처리할까?
                - 일단 sender에 있는 물 한계 생각 안하고 그냥 다 붓기
                - 최대 물 양이 넘칠 경우, 넘치는 양만큼 sender로 다시 붓고, receiver는 가질 수 있는 최대 물 양으로 설정
    

---

너비 우선 탐색(BFS)

그래프 완전 탐색 기번 중 하나로, 그래프의 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

너비 우선 탐색의 핵심 이론

 

• 한번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요
• 그래프는 인접 리스트로 표현
• DFS의 탐색 방식은 선입 선출 특성을 가짐 ( 큐 사용 )

 

알고리즘

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화

Do It! 알고리즘 코딩 테스트

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입 (이를 모든 정점에 다한다)

 

Do It! 알고리즘 코딩 테스트

만약 큐에 노드가 없으면, 방문하지 않은 정점을 알아내, 큐에 삽입하고 다시 2번 단계를 반복한다.

---

코드

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

public class Main {
    // 확인해야할 sender -> receiver 정리
    static int[] sender = {0,0,1,1,2,2};
    static int[] receiver = {1,2,0,2,0,1};

    // a가 비워졌을 때 c의 값일 경우에만 true
    static boolean [] results = new boolean[201];
    static boolean [][] visited = new boolean[201][201];
    static int [] input = new int[3];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // A,B,C 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        input[0] = Integer.parseInt(st.nextToken());
        input[1] = Integer.parseInt(st.nextToken());
        input[2] = Integer.parseInt(st.nextToken());

        BFS();

        // true인 경우만 i 출력 (그때가 a가 비워졌을 때, c가 가능한 값)
        for(int i=0;i<=input[2];i++) {
            if (results[i]) System.out.print(i + " ");
        }
    }

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

        while(!queue.isEmpty()) {
            AB now = queue.poll();
            int A = now.A;
            int B = now.B;
            int C = input[2] - (now.A + now.B);
            // 가능한 6개의 케이스 반복
            for(int i=0;i<6;i++) {
                int[] next = {A,B,C};
                // sender에 있는 물 한계 생각 안하고 그냥 다 붓기
                next[receiver[i]] += next[sender[i]];
                next[sender[i]] = 0;
                // 가능한 양이 넘칠 경우,
                // 넘치는 양만큼 sender로 이동시키고
                // receiver는 가질 수 있는 최댓값으로
                int reciver = receiver[i];
                if(next[reciver] > input[reciver]) {
                    next[sender[i]] = next[reciver] - input[reciver];
                    next[reciver] = input[reciver];
                }
                int a = next[0];
                int b = next[1];
                // 아직 확인하지 않은 경우
                if(!visited[a][b]) {
                    queue.add(new AB(a, b));
                    visited[a][b] = true;
                    // a가 0인 경우
                    if(a == 0)
                        results[input[2] - (a+b)] = true;
                }
            }
        }
    }

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