[2251] 물통

✔ 물통

[백준 2251]

문제 분석하기

그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이므로

A, B, C의 특정 무게 상태를 1개의 노드로 가정하고,

조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 엣지로 이어진 인접한 노드라고 생각하며 문제에 접근

손으로 풀어보기

1. 처음에 물통 A, B는 비어 있고, C는 꽉 차 있으므로 최초 출발 노드를 0, 0, 3번째 물통의 용량으로 초기화
2. BFS를 수행
   • 노드에서 갈 수 있는 6개의 경우(A → B, A → C, B → A, B → C, C → A, C → B)에 관해 다음 노드로 정해 큐에 추가함
     (A, B, C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않음)
   • 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장함
     (단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남김)
   • 큐에 추가하는 시점에 1번째 물통의 무게가 0일 때가 있으면 3번째 물통의 값을 정답 배열에 추가함
3. 정답 리스트를 오름차순으로 출력

예) 0, 0, 0

데이터 p	k = 0 A → B	k = 1 A → C	k = 2 B → A	k = 3 B → C	k = 4 C → A	k = 5 C → B	queue
							(0, 0)
(0, 0) 0, 0, 10	0, 0, 10	0, 0, 10	0, 0, 10	0, 0, 10	8, 0, 2	0, 9, 1	(8, 0), (0, 9)
(8, 0) 8, 0, 2	0, 8, 2	0, 0, 10	8, 0, 2	8, 0, 2	8, 0, 2	8, 2, 0	(0, 9), (0, 8), (8, 2)
(0, 9) 0, 9, 1	0, 9, 1	0, 9, 1	8, 1, 1	0, 0, 10	1, 9, 0	0, 9, 1	(0, 8), (8, 2), (8, 1), (1, 9)
(0, 8) 0, 8, 2	0, 8, 2	0, 8, 2	8, 0, 2	0, 0, 10	2, 8, 0	0, 9, 1	(8, 2), (8, 1), (1, 9), (2, 8)
(8, 2) 8, 2, 0	1, 9, 0	0, 2, 8	8, 2, 0	8, 0, 2	8, 2, 0	8, 2, 0	(8, 1), (1, 9), (2, 8), (0, 2)
(8, 1) 8, 1, 1	0, 9, 1	0, 1, 9	8, 1, 1	8, 0, 2	8, 1, 1	8, 2, 0	(1, 9), (2, 8), (0, 2), (0, 1)
(1, 9) 1, 9, 0	1, 9, 0	0, 9, 1	8, 2, 0	1, 0, 9	1, 9, 0	1, 9, 0	(2, 8), (0, 2), (0, 1), (1, 0)
(2, 8) 2, 8, 0	1, 9, 0	0, 8, 2	8, 2, 0	2, 0, 8	2, 8, 0	2, 8, 0	(0, 2), (0, 1), (1, 0), (2, 0)
(0, 2) 0, 2, 8	0, 2, 8	0, 2, 8	2, 0, 8	0, 0, 10	8, 2, 0	0, 9, 1	(0, 1), (1, 0), (2, 0)
(0, 1) 0, 1, 9	0, 1, 9	0, 1, 9	1, 0, 9	0, 0, 10	8, 1, 1	0, 9, 1	(1, 0), (2, 0)
(1, 0) 1, 0, 9	0, 1, 9	0, 0, 10	1, 0, 9	1, 0, 9	8, 0, 2	1, 9, 0	(2, 0)
(2, 0) 2, 0, 8	0, 2, 8	0, 0, 10	2, 0, 8	2, 0, 8	8, 0, 2	2, 8, 0

depth1	depth2	depth3	depth4	depth5
0, 0, 10	8, 0, 2	0, 8, 2	2, 8, 0	2, 0, 8
		8, 2, 0	0, 2, 8
		0, 0, 10
	0, 9, 1	8, 1, 1	0, 1, 9
		1, 9, 0	1, 0, 9
		0, 0, 10

슈도코드 작성하기

Sender, Receiver(6가지 경우를 탐색하기 위한 선언 배열)
answer(정답 배열)
now(A, B, C의 값을 저장하는 배열)
now 배열 저장하기
visited, answer 초기화 작업하기
BFS 수행하기
for(answer 배열 탐색하기) {
    answer 배열에서 값이 true인 index를 정답으로 출력하기
}

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

class AB {
    A, B 물통 무게를 변수로 가짐
}

코드 구현하기

/**
 * 2251) 물통
 */
public class D049_2251 {
    // Sender, Receiver(6가지 경우를 탐색하기 위한 선언 배열)
    // A → B, A → C, B → A, B → C, C → A, C → B
    static int[] Sender = { 0, 0, 1, 1, 2, 2 };
    static int[] Receiver = { 1, 2, 0, 2, 0, 1 };
    // visited(방문 기록 저장 배열)
    static boolean visited[][];
    // answer(정답 배열)
    static boolean answer[];
    // now(A, B, C의 값을 저장하는 배열)
    static int now[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // now 배열 저장하기
        now = new int[3];
        now[0] = sc.nextInt();
        now[1] = sc.nextInt();
        now[2] = sc.nextInt();
        // visited, answer 초기화 작업하기
        visited = new boolean[201][201];
        answer = new boolean[201];
        // BFS 수행하기
        BFS();
        // answer 배열에서 값이 true인 index를 정답으로 출력하기
        for (int i = 0; i < answer.length; i++) {
            if (answer[i])
                System.out.print(i + " ");
        }
    }

    public static void BFS() {
        // 큐 자료구조에 출발 노드 더하기
        Queue<AB> queue = new LinkedList<>();
        // A와 B가 0인 상태이므로 0, 0 노드에서 시작하기
        queue.add(new AB(0, 0));
        // visited 배열에 현재 노드 방문 기록하기
        visited[0][0] = true;
        // answer 배열에 현재 C의 값 체크하기
        answer[now[2]] = true;
        while (!queue.isEmpty()) {
            // 큐에서 노드 데이터를 가져오기
            AB p = queue.poll();
            // 데이터를 이용해 A, B, C의 값 초기화하기
            int A = p.A;
            int B = p.B;
            // C는 전체 물의 양에서 A와 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]];
                // 보내려는 물통 값을 0으로 업데이트하기
                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 배열에 방문 기록하기
                    visited[next[0]][next[1]] = true;
                    // 큐에 데이터 삽입
                    queue.add(new AB(next[0], next[1]));
                    // 1번째 물통이 비어 있을 때
                    if (next[0] == 0) {
                        // 3번째 물통의 물의 양을 answer 배열에 기록하기
                        answer[next[2]] = true;
                    }
                }
            }
        }
    }
}

// AB 클래스 선언
// A와 B의 값만 지니고 있으면 C는 유추할 수 있으므로 두 변수만 사용
class AB {
    // A, B 물통 무게를 변수로 가짐
    int A;
    int B;

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