✔ 물통
문제 분석하기
그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이므로
A, B, C의 특정 무게 상태를 1개의 노드로 가정하고,
조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 엣지로 이어진 인접한 노드라고 생각하며 문제에 접근
손으로 풀어보기
- 처음에 물통 A, B는 비어 있고, C는 꽉 차 있으므로 최초 출발 노드를 0, 0, 3번째 물통의 용량으로 초기화
- BFS를 수행
- 노드에서 갈 수 있는 6개의 경우(A → B, A → C, B → A, B → C, C → A, C → B)에 관해 다음 노드로 정해 큐에 추가함
(A, B, C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않음) - 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장함
(단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남김) - 큐에 추가하는 시점에 1번째 물통의 무게가 0일 때가 있으면 3번째 물통의 값을 정답 배열에 추가함
- 노드에서 갈 수 있는 6개의 경우(A → B, A → C, B → A, B → C, C → A, C → B)에 관해 다음 노드로 정해 큐에 추가함
- 정답 리스트를 오름차순으로 출력
예) 0, 0, 0
데이터 p | k = 0 A → B |
k = 1 A → C |
k = 2 B → A |
k = 3 B → C |
k = 4 C → A |
k = 5 C → B |
queue |
(0, 0) | |||||||
(0, 0) 0, 0, 10 |
0, 0, 10 | 0, 0, 10 | 0, 0, 10 | 0, 0, 10 | 8, 0, 2 | 0, 9, 1 | (8, 0), (0, 9) |
(8, 0) 8, 0, 2 |
0, 8, 2 | 0, 0, 10 |
8, 0, 2 | 8, 0, 2 | 8, 0, 2 | 8, 2, 0 | (0, 9), (0, 8), (8, 2) |
(0, 9) 0, 9, 1 |
0, 9, 1 | 0, 9, 1 | 8, 1, 1 | 0, 0, 10 |
1, 9, 0 | 0, 9, 1 | (0, 8), (8, 2), (8, 1), (1, 9) |
(0, 8) 0, 8, 2 |
0, 8, 2 | 0, 8, 2 | 8, 0, 2 | 0, 0, 10 |
2, 8, 0 | 0, 9, 1 | (8, 2), (8, 1), (1, 9), (2, 8) |
(8, 2) 8, 2, 0 |
1, 9, 0 | 0, 2, 8 | 8, 2, 0 | 8, 0, 2 | 8, 2, 0 | 8, 2, 0 | (8, 1), (1, 9), (2, 8), (0, 2) |
(8, 1) 8, 1, 1 |
0, 9, 1 | 0, 1, 9 | 8, 1, 1 | 8, 0, 2 | 8, 1, 1 | 8, 2, 0 | (1, 9), (2, 8), (0, 2), (0, 1) |
(1, 9) 1, 9, 0 |
1, 9, 0 | 0, 9, 1 | 8, 2, 0 | 1, 0, 9 | 1, 9, 0 | 1, 9, 0 | (2, 8), (0, 2), (0, 1), (1, 0) |
(2, 8) 2, 8, 0 |
1, 9, 0 | 0, 8, 2 | 8, 2, 0 | 2, 0, 8 | 2, 8, 0 | 2, 8, 0 | (0, 2), (0, 1), (1, 0), (2, 0) |
(0, 2) 0, 2, 8 |
0, 2, 8 | 0, 2, 8 | 2, 0, 8 | 0, 0, 10 | 8, 2, 0 | 0, 9, 1 | (0, 1), (1, 0), (2, 0) |
(0, 1) 0, 1, 9 |
0, 1, 9 | 0, 1, 9 | 1, 0, 9 | 0, 0, 10 | 8, 1, 1 | 0, 9, 1 | (1, 0), (2, 0) |
(1, 0) 1, 0, 9 |
0, 1, 9 | 0, 0, 10 | 1, 0, 9 | 1, 0, 9 | 8, 0, 2 | 1, 9, 0 | (2, 0) |
(2, 0) 2, 0, 8 |
0, 2, 8 | 0, 0, 10 | 2, 0, 8 | 2, 0, 8 | 8, 0, 2 | 2, 8, 0 |
depth1 | depth2 | depth3 | depth4 | depth5 |
0, 0, 10 | 8, 0, 2 | 0, 8, 2 | 2, 8, 0 | 2, 0, 8 |
8, 2, 0 | 0, 2, 8 | |||
0, 0, 10 | ||||
0, 9, 1 | 8, 1, 1 | 0, 1, 9 | ||
1, 9, 0 | 1, 0, 9 | |||
0, 0, 10 |
슈도코드 작성하기
Sender, Receiver(6가지 경우를 탐색하기 위한 선언 배열)
answer(정답 배열)
now(A, B, C의 값을 저장하는 배열)
now 배열 저장하기
visited, answer 초기화 작업하기
BFS 수행하기
for(answer 배열 탐색하기) {
answer 배열에서 값이 true인 index를 정답으로 출력하기
}
BFS {
큐 자료구조에 출발 노드 더하기 -> A와 B가 0인 상태이므로 0, 0 노드에서 시작하기
visited 배열에 현재 노드 방문 기록하기
answer 배열에 현재 C의 값 체크하기
while(큐가 빌 때까지) {
큐에서 노드 데이터를 가져오기(poll 연산)
데이터를 이용해 A, B, C의 값 초기화하기
for(6가지 케이스 반복하기) {
받는 물통에 보내려는 물통의 값 더하기
보내려는 물통 값을 0으로 업데이트하기
if(받는 물통이 넘칠 때) {
넘치는 만큼 보내는 물통에 다시 넣어 주고, 받는 물통은 이 물통의 최댓값으로 저장
}
현재 노드의 연결 노드 중 방문하지 않은 노드로
큐에 데이터 삽입(add 연산)하고 visited 배열에 방문 기록하기
if(1번째 물통이 비어 있을 때) {
3번째 물통의 물의 양을 answer 배열에 기록하기
}
}
}
}
class AB {
A, B 물통 무게를 변수로 가짐
}
코드 구현하기
/**
* 2251) 물통
*/
public class D049_2251 {
// Sender, Receiver(6가지 경우를 탐색하기 위한 선언 배열)
// A → B, A → C, B → A, B → C, C → A, C → B
static int[] Sender = { 0, 0, 1, 1, 2, 2 };
static int[] Receiver = { 1, 2, 0, 2, 0, 1 };
// visited(방문 기록 저장 배열)
static boolean visited[][];
// answer(정답 배열)
static boolean answer[];
// now(A, B, C의 값을 저장하는 배열)
static int now[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// now 배열 저장하기
now = new int[3];
now[0] = sc.nextInt();
now[1] = sc.nextInt();
now[2] = sc.nextInt();
// visited, answer 초기화 작업하기
visited = new boolean[201][201];
answer = new boolean[201];
// BFS 수행하기
BFS();
// answer 배열에서 값이 true인 index를 정답으로 출력하기
for (int i = 0; i < answer.length; i++) {
if (answer[i])
System.out.print(i + " ");
}
}
public static void BFS() {
// 큐 자료구조에 출발 노드 더하기
Queue<AB> queue = new LinkedList<>();
// A와 B가 0인 상태이므로 0, 0 노드에서 시작하기
queue.add(new AB(0, 0));
// visited 배열에 현재 노드 방문 기록하기
visited[0][0] = true;
// answer 배열에 현재 C의 값 체크하기
answer[now[2]] = true;
while (!queue.isEmpty()) {
// 큐에서 노드 데이터를 가져오기
AB p = queue.poll();
// 데이터를 이용해 A, B, C의 값 초기화하기
int A = p.A;
int B = p.B;
// C는 전체 물의 양에서 A와 B를 뺀 것
int C = now[2] - A - B;
for (int k = 0; k < 6; k++) {
int[] next = { A, B, C };
// 받는 물통에 보내려는 물통의 값 더하기
next[Receiver[k]] += next[Sender[k]];
// 보내려는 물통 값을 0으로 업데이트하기
next[Sender[k]] = 0;
// 받는 물통이 넘칠 때
if (next[Receiver[k]] > now[Receiver[k]]) {
// 넘치는 만큼 보내는 물통에 다시 넣어 주고
next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
// 받는 물통은 이 물통의 최댓값으로 저장
next[Receiver[k]] = now[Receiver[k]];
}
// 현재 노드의 연결 노드 중 방문하지 않은 노드로
if (!visited[next[0]][next[1]]) {
// visited 배열에 방문 기록하기
visited[next[0]][next[1]] = true;
// 큐에 데이터 삽입
queue.add(new AB(next[0], next[1]));
// 1번째 물통이 비어 있을 때
if (next[0] == 0) {
// 3번째 물통의 물의 양을 answer 배열에 기록하기
answer[next[2]] = true;
}
}
}
}
}
}
// AB 클래스 선언
// A와 B의 값만 지니고 있으면 C는 유추할 수 있으므로 두 변수만 사용
class AB {
// A, B 물통 무게를 변수로 가짐
int A;
int B;
public AB(int A, int B) {
this.A = A;
this.B = B;
}
}
'Coding Test > 알고리즘 실전' 카테고리의 다른 글
[1043] 거짓말 (0) | 2023.09.21 |
---|---|
[1976] 여행 가자 (0) | 2023.09.21 |
[1325] 효율적인 해킹 (0) | 2023.09.18 |
[18352] 특정 거리의 도시 찾기 (0) | 2023.09.18 |
[21568] Ax+By=C (0) | 2023.09.17 |