백준 2251. 물통

백준 2251. 물통

문제

입력

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

출력

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

풀이

문제가 그래프 단원에 실려있어서 어떻게 그래프로 접근해야할지 생각해본 것 같다. 그래프 단원이 아니었다면 그래프로 생각해볼 수 있었을까...
여하튼 그래서 그래프로 연결된 구조부터 생각했다. 각 물통은 자신이 아닌 다른 물통에 물을 몽땅 부을 수 있으므로 자신을 제외한 모든 물통들과 양방향으로 연결되어 있는 그래프이다. 그래서 아마 각 물통의 연결관계를 갖는 배열을 선언하는 것까지는 생각해낸 것 같다.
A, B, C를 순차적으로 0, 1, 2 라고 하면
graph = [[1,2],[0,2],[0,2]]로 각 노드의 연결관계는 인덱스 0, 1, 2 로 접근할 수 있다.

그리고 a와 b의 물의 양을 bfs를 위한 방문 배열로 사용할 것이다. 그래서 boolean[][] ab = new boolean[201][201]로 선언하였다.
a와 b의 물의 양을 가지고 c의 물의 양을 판단할 수 있다.

초기에 a와 b의 물의 양은 0,0 이므로 ab[0][0] = true;로 방문처리를 하고, queue.add(new int[]{0,0});을 큐에 넣고 bfs를 시작한다.

next[]에는 큐에서 꺼낸 값을 이용하여 c값을 구해 물의 상태를 표현한다.
그리고 각 물통에 연결된 다른 물통에 물을 부어 visited 배열을 갱신하면서 탐색한다.
bfs가 방문할 수 있는 총 경우의 수는 6가지이다. <-- graph[] 를 탐색한다는 뜻

나는 내가 생각할 수 있는 범주내에서 풀이를 하려한다. 그래서 위와 같이 2차원 배열 graph를 만들어서 접근하려 했고, 책에서 풀이는 아래와 같은 배열을 2개 두었다.

sender = [0,0,1,1,2,2]
receiver = [1,2,0,2,0,1]

for (int i = 0; i < 6; i++)
	sender[i]
    receiver[i]

똑같이 6가지를 탐색하게 된다.
또한 나는 큐에 삽입할 때 배열의 형태로 넣었는데, 풀이로는 클래스를 따로 선언하여 a와 b의 물을 저장하여 큐에 삽입하는 형태를 취했다. 이 또한 이것에 익숙하지 않은 내가 문제를 접하게 되었을 때 생각나지 않을 것 같아서 나만의 풀이로 해결했다.
메모리 효율적인 면에서는 모르겠으나 알고리즘은 제대로 구성하였으므로, 접근 방법에 대한 것만 잘 숙지하도록 해야겠다.

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 boj2251 {

    static int A, B, C;
    static int[] water;
    static boolean[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        A = Integer.parseInt(stk.nextToken());
        B = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());

        water = new int[]{A, B, C};
        answer = new boolean[201];

        bfs();

        for (int i = 0; i < 201; i++) {
            if (answer[i]) {
                System.out.print(i+" ");
            }
        }
    }

    public static void bfs() {
        boolean[][] ab = new boolean[201][201];
        int[][] graph = {{1, 2}, {0, 2}, {0, 1}};

        answer[C] = true;
        ab[0][0] = true;

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int a = node[0];
            int b = node[1];
            int c = C - a - b;

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 2; j++) {
                    int[] next = {a, b, c}; // 현재 물상태. 이 물상태를 갖고 물을 이동시키며 판단할 것이기 때문

                    next[i] = next[i] + next[graph[i][j]];
                    next[graph[i][j]] = 0;
                    if (next[i] > water[i]) {
                        next[graph[i][j]] = next[i] - water[i];
                        next[i] = water[i];
                    }

                    if (!ab[next[0]][next[1]]){
                        ab[next[0]][next[1]] = true;
                        queue.add(new int[]{next[0], next[1]});
                        if (next[0] == 0) {
                            answer[next[2]] = true;
                        }

                    }

                }
            }
        }
    }
}