2251 물통

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

2251번: 물통

각 물통의 특징에 유의해서 보자. 모든 물통의 용량이 200이하 이고, 3개이다. 즉, 3가지 물통의 상태를 3차원 배열로 나타낼 수 있다.

이를 바탕으로 bfs를 수행하면 모든 상태를 탐색할 수 있다. 방문한 상태를 다시 탐색하지 않기 때문이다.

답을 구하는 과정은 중간에 첫 번째 물통의 용량이 0일 때 TreeSet에 넣도록 했다.

 

고찰:

물통의 물을 다른 물통에 옮기는 과정을 구현하지 못했다. bfs까지는 떠올렸지만 탐색을 구현하는 부분만 답을 참고했다.

 

정답코드

import java.io.*;
import java.util.*;
class Node{
  int a, b, c;
  public Node(int a, int b, int c){
    this.a = a;
    this.b = b;
    this.c = c;
  }
}
public class Main {
  private static int A, B, C;
  private static boolean[][][] visit = new boolean[201][201][201];
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    A = Integer.parseInt(st.nextToken());
    B = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());

    Queue<Node> q = new LinkedList<>();
    q.add(new Node(0, 0, C));

    TreeSet<Integer> answer = new TreeSet<>();
    answer.add(C);

    while(!q.isEmpty()){
      int a = q.peek().a;
      int b = q.peek().b;
      int c = q.peek().c;
      q.poll();
      if(visit[a][b][c])
        continue;
      visit[a][b][c] = true;
      if(a == 0) answer.add(c);

      //A -> B
      if(a + b > B) q.add(new Node((a + b - B), B, c));
      else q.add(new Node(0, a + b, c));

      //A -> C
      if(a + c > C) q.add((new Node((a + c - C), b, C)));
      else q.add(new Node(0, b, a + c));

      //B -> A
      if(b + a > A) q.add((new Node(A, (a + b - A), c)));
      else q.add(new Node(a + b, 0, c));
      //B -> C
      if(b + c > C) q.add((new Node(a, (b + c - C), C)));
      else q.add(new Node(a, 0, b + c));
      //C -> A
      if(a + c > A) q.add((new Node(A, b, (a + c - A))));
      else q.add(new Node(a + c, b, 0));
      //C -> B
      if(b + c > B) q.add((new Node(a, B, (b + c - B))));
      else q.add(new Node(a, b + c, 0));
    }
    for (Integer i : answer)
      System.out.print(i + " ");
    System.out.println();
  }
}