코딩 테스트 [그래프] - 물의 양 구하기

각각 부피가 A, B, C(1 ≤ A, B, C ≤ 200) 리터인 3개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 3번째 물통(C 리터)은 가득 차 있다. 이제 어떤 물통에 들어 있는 물을 다른 물통으로 쏟아부을 수 있는데, 이때는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다 보면 3번째 물통(용량이 C인)에 담겨 있는 물의 양이 변할 수도 있다. 1반째 물통(용량이 A인)이 비어 있을 때 3번째 물통(용량이 C인)에 담겨 있을 수 있는 물의 양을 모두 구하는 프로그램을 작성하시오.

(시간 제한 1초)

---

입력

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

출력

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

예제 입력
8 9 10	// A B C

예제 출력
1 2 8 9 10

---

1단계 - 문제 분석하기

그래프로 데이터를 저장하고 작성하는 자료구조를 이용하는 방식과 달리, 그래프의 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다.
A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접 노드라고 생각하고 문제에 접근해 보자.

2단계 - 손으로 풀어 보기

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

2 BFS를 수행한다. 탐색 과정은 다음과 같다.

BFS 과정
1. 노드에서 갈 수 있는 6개의 경우(A → B, A → C, B → A, B → C, C → A, C → B)에 관해 다음 노드로 정해 큐에 추가한다. A, B, C 무게가 동일한 노드에 방문 이력이 있을 때는 큐에 추가하지 않는다.
2. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통이 넘칠 때는 초과하는 값 만큼 보내는 물통에 남긴다.
3. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 배열에 추가한다.

3 정답 리스트를 오름차순 출력

10 1 2 8 9를 오름차순으로 정렬 후 출력 ⇒ 1 2 8 9 10

3단계 - sudo코드 작성하기

Sender, Receiver (6가지 경우를 탐색하기 위한 선언 배열)
visited(방문 배열 저장)
answer(정답 배열)
now(A, B, C 값을 저장하는 배열)

now 배열 저장하기
visited, answer 초기화

BFS 수행

for(answer 배열 탐색)
	answer 배열에서 값이 true인 index 정답으로 출력

BFS {
	큐 자료구조에 출발 노드 추가(0, 0, C 노드에서 시작)
    visited 배열에 현재 노드 추가
    answer 배열에 현재 C값 체크 (A가 0으로 시작하기 때문에)
    
    while(큐가 빌 때 까지)
    {
    	큐에서 노드 가져오기(poll)
        데이터를 이용해 A, B, C값 초기화
        
        for(6가지 케이스 반복)
        {
        	받는 물통에 보내려는 물통의 값 더하기
            보내려는 물통 값을 0으로 업데이트
            
            if(받는 물통이 넘칠 때)
            {
            	넘치는 만큼 보내는 물통에 다시 넣기.
                받는 물통을 물통의 최댓값으로 저장
            }
            현재 노드의 연결 노드 중 방문하지 않은 노드로 이동
            큐에 데이터 삽입(add)하고 visited 배열에 방문 기록
            
            if(1번째 물통이 비어 있을 때)
            	3번째 물통의 물의 양을 answer 배열에 기록
        }
    }
}

// A, B 클래스 선언(A, B값만 지니고 있으면 C값은 유추할 수 있으므로 A, B만 저장)
class AB {
	A, B 물통 무게를 변수로 지님.
}

4단계 - 코드 구현하기

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

public class Q49 {
    //  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[];
    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;

            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]];
                }

                if(!visited[next[0]][next[1]]){
                    visited[next[0]][next[1]] = true;
                    queue.add(new AB(next[0], next[1]));
                    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;
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편