1. ๋ฌธ์ ์ค๋ช ๐
(1) ๋งํฌ๐
(2) ํด์ค๐ต
- A,B,C ๋ฌผํต์ ์ฉ๋์ด ์ฃผ์ด์ง๊ณ , A,B๋ ๋น์ด ์๋ ์ํ, C๋ ๊ฐ๋์ฐฌ ์ํ๋ก ์ฃผ์ด์ง๋ค.
- A ๋ฌผํต์ด ๋น์ด ์์ ์ ์๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์์์ C์ ์ฐฌ ๋ฌผ์ ์ฉ๋์ ์ถ๋ ฅ ํ์์ค
2. ์๊ฐ์ ํ๋ฆ: ์ฝ๋๊ฐ ๋์ค๊ธฐ๊น์ง ๐๏ธ
(1) IDEA ๋์ถ๐ก
KEY WORD: Back-tracking
์ด ๋ฌธ์ ๋ฅผ ์ฒ์๋ณด๊ณ , ํ๋ ธ์ด์ ํ์ด ๋ ์ฌ๋๋ค. ์ด์ ๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ํ๋์ ๋ฌผํต์์ ๋ค๋ฅธ ๋ฌผํต์ผ๋ก ์ ๋ฌํ ์ ์๋ ๋ฌผ์ ์ฉ๋์ด ์ ํด์ง
์ด ๋ถ๋ถ ๋๋ฌธ์ ๋ฌผ์ด๋ผ๋, ๋ณด๋ด์ง ์์ ์ ํํํ ์ ์๊ธฐ ๋๋ฌธ์, ํ๋ ธ์ด์ ํ๊ณผ ๋ค๋ฅผ ๋ฐ ์๋ค๊ณ ๋๊ผ๋ค. ๋ฐ๋ผ์ Back-tracking์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์๋ค.
์ดํ ๊ตฌํ ๋ฐฉ์
Bottle3๋ผ๋ ํด๋์ค๋ฅผ ๋ง๋ค์ด์, hashCode()์ equals() ํจ์๋ฅผ ์ด๊ธฐํ ํ๋ค. ์ด์ ๋ *HashSet์ ๋ฃ์ด์, ์ค๋ณต๋ ๊ฐ์ ์นด์ดํธ ํ์ง ์๊ธฐ ์ํด์ *์ด๋ค.- ์ค๋ณต๋ ๊ฐ์ด๋ฉด ๋์ด๊ฐ๊ณ , ์ฒ์๋ณด๋ A,B,C ์์์ด๋ฉด SET์ ๋ฃ๋๋ค.
- ๋ง์ฝ SET์ ๋ฃ์ ๋ A๊ฐ 0์ด๋ฉด, C๋ฅผ ๋ต๋ณ์ง List์ ์ ์ฅํ๋ค.
(2) SUDO CODE ๐
+ 0. ์ธํ
- ๋ฌผํต ํด๋์ค๋ฅผ ๋ง๋ค์ด์, hashCode()์ equals ํจ์ ์ด๊ธฐํ
+ 0. ์
๋ ฅ๊ฐ ๋ฐ์์, A,B,C ์ต๋ ์ฉ๋์ ๋ํ๋ด๋ volume ๋ฐฐ์ด์ ๋ฃ๊ธฐ
+ 1. Back-tracking ์์(from = ๊ทผ์์ง, to = ํ์ ,int [] arr ํ ๋ ๋ฒจ ๋ฌผ์ ์์ snapShot)
- (1) from์์ to๋ก ์ฎ๊ฒจ ๋ด๊ธฐ
- (2) ์ฎ๊ฒจ ๋ด์ ํ A,B,C์ ๋ฌผ์ด ๋ด๊ธด ์์์ด ์ฒ์ ๋ณด๋ ๊ฑฐ๋ฉด SET์ ๋ฃ๊ณ , ๋ค์์ผ๋ก ๋์ด๊ฐ
- ๋ง์ฝ ํ ๋ฒ ๋ณธ ์์์ด๋ฉด, ์ด๋ฒ Back-tracking์ ์ข
๋ฃํ๊ณ ๋ถ๋ชจ ๋ ๋ฒจ๋ก ๋์๊ฐ๋ค.
- (3) A,B,C์ ์์์์ A = 0 ์ด๋ฉด C๊ฐ์ ๋ต๋ณ ๋ฆฌ์คํธ์ ์ ์ฅํ๋ค.
- (4) ํ ์์์์ ๋ค์ ์ฎ๊ฒจ ๋ด๊ธฐ๋ฅผ ๋ฐ๋ณตํ๋ค. from๊ณผ to๋ฅผ ํ Level๊ณผ ๋๊ฐ์ง ์๊ณ , from์ ๋ฌผ์ด ๋ด๊ธด ๊ฑฐ๋ฉด ์ ๋ถ ์๋
(3) ์๊ฐ๋ณต์ก๋ ๋ถ์ ๐
A,B,C ์ ์ฒด ๋ฌผ์ ์ฉ๋์ด ์ต๋ 200๋ฐ์ ์๋์ ์ํ์ผ๋ก ํ์ด๋ ๊ฐ๋ฅํ ์์ค์ด์๋ค. ๊ทธ๋์ Back-Tracking์ ์ ํํ๋ค.
๋ค๋ฅธ ์ฌ๋๋ค์ ํ์ด๋ฅผ ๋ณด๋๊น, A,B,C ๋ฌผํต์์ ๋์ฌ ์ ์๋ ๋ชจ๋ ์์์ boolean [201][201][201] ๋ก ํํํด์,๋ฐฐ์ด ๋ด์ BFS๋ก ๋ฌธ์ ๋ฅผ ํธ์ ๋ถ๋ค๋ ์๋๋ผ. ์ด ๊ฒฝ์ฐ, ๋ด ํ์ด๋ณด๋ค ์๊ฐ์ด 2๋ฐฐ ๋นจ๋๋ค.
3. ๊ตฌํ ์ฝ๋ ๐
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
static int [] volume = new int [3];
static HashSet<Bottle3> set = new HashSet<>();
static ArrayList<Integer> ans = new ArrayList<>();
public static void main(String[] args) throws IOException {
init();
back_tracking(2, 0, new int []{0,0,volume[2]});
back_tracking(2, 1, new int []{0,0,volume[2]});
Collections.sort(ans);
for (int answer : ans) {
System.out.print(answer + " ");
}
}
public static void init() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
volume[0] = Integer.parseInt(st.nextToken());
volume[1] = Integer.parseInt(st.nextToken());
volume[2] = Integer.parseInt(st.nextToken());
}
public static void back_tracking(int from, int to, int [] arr) {
// ๊ณ์ฐ ์กฐ๊ฑด
int origin_from = arr[from];
arr[from] = (volume[to] - arr[to]) - arr[from] >= 0 ? 0 : arr[from] - (volume[to] - arr[to]);
arr[to] = (volume[to] - arr[to]) - origin_from >= 0 ? arr[to] + origin_from : volume[to];
Bottle3 now = new Bottle3(arr[0], arr[1], arr[2]);
if(set.contains(now)) return;
else {
if(arr[0] == 0)ans.add(arr[2]);
set.add(now);
}
for(int i = 0; i < 3; i++){
if(arr[i] > 0) {
for (int j = 0; j < 3; j++) {
if(i != j && (i != from && j != to)){
back_tracking(i, j, new int []{arr[0], arr[1], arr[2]});
}
}
}
}
}
}
class Bottle3 {
int A;
int B;
int C;
public Bottle3 (int A, int B, int C) {
this.A = A;
this.B = B;
this.C = C;
}
@Override
public boolean equals (Object obj) {
if(obj.getClass()!= Bottle3.class) return false;
return ((Bottle3) obj).A == this.A
&& ((Bottle3) obj).B == this.B
&& ((Bottle3) obj).C == this.C;
}
@Override
public int hashCode() {
return this.A + this.B + this.C;
}
}
4. ๋ฐฐ์ด ๊ฒ๋ค ๐ฏ
(1) ์ค๋๋ง์ ์ฐ๋ equals, hashcode ์ฌ์ ์
equal์ ์ธ์๋ก Object obj๊ฐ ๋ค์ด๊ฐ๋ค๋ ๊ฒ์ ๋งค๋ฒ ๊น๋จน๋๋ค. ๊ทธ๋ฆฌ๊ณ , equals์ ์ธ์๊ฐ Object์์ผ๋ก, ํ์ฌ ์ฌ์ ์ํ ๊ฐ์ฒด์ ํด๋์ค์ ๋์ผ ํด๋์ค์ธ์ง, ํด๋์ค ์ฒดํฌ๋ฅผ ํด์ค์ผ ํ๋ค๋ ์ฌ์ค๋ ์์ง ๋ง์.
์ด๋ชจ์ง ๋ชจ์: ๐ค, โ โจ 0๏ธโฃ1๏ธโฃ2๏ธโฃ3๏ธโฃ4๏ธโฃ5๏ธโฃ6๏ธโฃ7๏ธโฃ8๏ธโฃ9๏ธโฃ๐