백준 물통(2251)

DFS 문제를 풀어보았다.

 

https://www.acmicpc.net/problem/2251

2251번: 물통

 

물통은 A B C개가 존재하며

 

물은 한통에서 다른 통으로 옮긴다라는 하나의 액션을 생각해보면 된다.

 

내가 현재 잡은 물통에 물이 있으면 나머지 통에 옮길수 있을만큼 옮기면 된다.

 

키 포인트

• 선택한 물통을 다른 물통으로 옮길 수 있는 만큼 옮기기
• 몰통들의 수량 케이스를 담아서 방문기록 유지하기

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    private static HashSet<String> set = new HashSet<>();

    private static PriorityQueue<Integer> answer = new PriorityQueue<>();

    private static int[] max;

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        max = new int[]{A, B, C};

        dfs(0, 0, C);

        StringBuffer sb = new StringBuffer();
        while (!answer.isEmpty()) {
            sb.append(answer.poll()).append(" ");
        }


        System.out.println(sb.toString());
    }


    public static void dfs(int A, int B, int C) {

        String val = "" + A + B + C;
        if (set.contains(val)) return;
        set.add(val);

        if (A == 0) {
            answer.add(C);
        }

        if (A != 0) {
            dfs(A - cal(A, B, max[1]), B + cal(A, B, max[1]), C);
            dfs(A - cal(A, C, max[2]), B, C + cal(A, C, max[2]));
        }

        if (B != 0) {
            dfs(A + cal(B, A, max[0]), B - cal(B, A, max[0]), C);
            dfs(A, B - cal(B, C, max[2]) , C + cal(B, C, max[2]));
        }

        if (C != 0) {
            dfs(A + cal(C, A, max[0]), B, C - cal(C, A, max[0]));
            dfs(A, B + cal(C, B, max[1]) , C - cal(C, B, max[1]));
        }

    }

    public static int cal(int A, int B, int max) {
        return Math.min(max - B, A);
    }
}

 

 

결과