물통

문제 출처 : Baekjoon Online Judge 2251번 "물통" - https://www.acmicpc.net/problem/2251

완전 탐색 강의를 들으면서 접한 문제이다. 이러한 종류의 탐색 문제를 푸는 방법은 n중 for문, 큐, 순열, 재귀, 비트마스크 등이 있는데, 이번에는 큐를 사용한 bfs로 문제를 풀었다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
class Abc {
    public int a;
    public int b;
    public int c;
 
    public Abc(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}
 
public class WaterBucket {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Queue<Abc> q = new LinkedList<>();
        boolean ans[] = new boolean[201];
        boolean visit[][][] = new boolean[201][201][201];
        int maxA, maxB, maxC;
 
        maxA = sc.nextInt();
        maxB = sc.nextInt();
        maxC = sc.nextInt();
 
        q.add(new Abc(0, 0, maxC));
 
        while (!q.isEmpty()) {
            int nowA, nowB, nowC;
 
            nowA = q.peek().a;
            nowB = q.peek().b;
            nowC = q.peek().c;
            
            q.remove();
 
            if (visit[nowA][nowB][nowC]) {
                continue;
            }
 
            visit[nowA][nowB][nowC] = true;
            if (nowA == 0) {
                ans[nowC] = true;
            }
 
            // c->a
            if (nowC != 0 && nowA < maxA) {
                int leftA = maxA - nowA;
                if (nowC > leftA)
                    q.add(new Abc(maxA, nowB, nowC - leftA));
                else
                    q.add(new Abc(nowA + nowC, nowB, 0));
            }
 
            // c->b
            if (nowC != 0 && nowB < maxB) {
                int leftB = maxB - nowB;
                if (nowC > leftB)
                    q.add(new Abc(nowA, maxB, nowC - leftB));
                else
                    q.add(new Abc(nowA, nowB + nowC, 0));
            }
 
            // b->a
            if (nowB != 0 && nowA < maxA) {
                int leftA = maxA - nowA;
                if (nowB > leftA)
                    q.add(new Abc(maxA, nowB - leftA, nowC));
                else
                    q.add(new Abc(nowA + nowB, 0, nowC));
            }
 
            // b->c
            if (nowB != 0 && nowC < maxC) {
                int leftC = maxC - nowC;
                if (nowB > leftC)
                    q.add(new Abc(nowA, nowB - leftC, maxC));
                else
                    q.add(new Abc(nowA, 0, nowC + nowB));
            }
 
            // a->c
            if (nowA != 0 && nowC < maxC) {
                int leftC = maxC - nowC;
                if (nowA > leftC)
                    q.add(new Abc(nowA - leftC, nowB, maxC));
                else
                    q.add(new Abc(0, nowB, nowC + nowA));
            }
 
            // a->b
            if (nowA != 0 && nowB < maxB) {
                int leftB = maxB - nowB;
                if (nowA > leftB)
                    q.add(new Abc(nowA - leftB, maxB, nowC));
                else
                    q.add(new Abc(0, nowB + nowA, nowC));
            }
        }
 
        for (int i = 0; i <= maxC; i++) {
            if (ans[i] == true)
                System.out.print(i + " ");
        }
    }
}
 

상태가 변할 수 있는 경우를 모두 생각하여 큐에 집어넣고, 하나씩 빼내어 다음 경우를 계산해주면 된다. 이렇게 쭉 가다가 결국 가능한 visit가 모두 차게되고 더이상 큐에 요소가 없어서 루프가 종료된다.

bfs를 사용하는 완전탐색 문제는 이렇게 큐를 쓴다는 형식이 고정되어있고, 문제에 맞는 상태 변화만 바꿔주면 된다고 하는데, 다른 문제들을 접해봐야 감이 올 것 같다.