반응형
https://www.acmicpc.net/problem/2251
2251번: 물통
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다.
www.acmicpc.net
BFS문제
문제의 제한값을 보면 A B C <=200 보다 작다는 것을 알수가 있다.
문제에서 할수 있는 경우의 수는 총 6 가지이다.
A->B, A->C
B->A,B->C
C->A,C->B
로 물을 붇는 경우의 수 밖에없다 . 이러한 각각의 상태등를 Q에 넣고 visit[200][200][200] 크기의 공간을 활용한다면 BFS로 쉽게 풀수가 있다. 물론 DFS도 가능하다.
package day0225;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
import day0225.B2251.LITER;
public class B2251 {
static int A,B,C;
static boolean liter[][][];
static TreeSet<Integer> set = new TreeSet<Integer>();
static class LITER{
int a;
int b;
int c;
public LITER(int a, int b, int c) {
super();
this.a = a;
this.b = b;
this.c = c;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
A = sc.nextInt();
B = sc.nextInt();
C = sc.nextInt();
int a = 0;
int b = 0;
int c = C;
Queue<LITER> q = new LinkedList<LITER>();
liter = new boolean[201][201][201];
liter[a][b][c] = true;
q.add(new LITER(a, b, c));
while(!q.isEmpty()) {
LITER tmp = q.poll();
a = tmp.a;
b = tmp.b;
c = tmp.c;
if(tmp.a==0) {
set.add(tmp.c);
}
//a->b
if(a+b>=B) {
if(!liter[a-(B-b)][B][c]) {
liter[a-(B-b)][B][c] = true;
q.add(new LITER(a-(B-b), B, c));
}
}else {
if(!liter[0][a+b][c]) {
liter[0][a+b][c] = true;
q.add(new LITER(0, a+b, c));
}
}
//a->c
if(a+c>=C) {
if(!liter[a-(C-c)][b][C]) {
liter[a-(C-c)][b][C] = true;
q.add(new LITER(a-(C-c),b,C));
}
}else {
if(!liter[0][b][a+c]) {
liter[0][b][a+c]=true;
q.add(new LITER(0, b, a+c));
}
}
//b->a
if(b+a>=A) {
if(!liter[A][b-(A-a)][c]) {
liter[A][b-(A-a)][c]=true;
q.add(new LITER(A,b-(A-a),c));
}
}else {
if(!liter[b+a][0][c]) {
liter[b+a][0][c]=true;
q.add(new LITER(b+a,0,c));
}
}
//b->c
if(b+c>=C) {
if(!liter[a][b-(C-c)][C]) {
liter[a][b-(C-c)][C] = true;
q.add(new LITER(a,b-(C-c),C));
}
}else {
if(!liter[a][0][b+c]) {
liter[a][0][b+c] = true;
q.add(new LITER(a,0,b+c));
}
}
//c->a
if(c+a>=A) {
if(!liter[A][b][c-(A-a)]) {
liter[A][b][c-(A-a)] = true;
q.add(new LITER(A,b,c-(A-a)));
}
}else {
if(!liter[c+a][b][0]) {
liter[c+a][b][0] = true;
q.add(new LITER(c+a,b,0));
}
}
//c->b
if(c+b>=B) {
if(!liter[a][B][c-(B-b)]) {
liter[a][B][c-(B-b)]=true;
q.add(new LITER(a,B,c-(B-b)));
}
}else {
if(!liter[a][c+b][0]) {
liter[a][c+b][0] = true;
q.add(new LITER(a,c+b,0));
}
}
}
Iterator<Integer> iter = set.iterator();
while(iter.hasNext()) {
System.out.print(iter.next() +" ");
}
}
}
반응형