49번 물통
책 풀이 해설
그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다. A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고 접근해야 된다.
처음에 물통 A, B는 비어 있고, C는 꽉 차 있으므로 최초 출발 노드를 0, 0, 3번째 물통의 용량으로 초기화한다. BFS를 탐색한다. BFS과정은 노드에서 갈 수 있는 6개 경우( A -> B, A -> C, B -> A, B -> C, C -> A, C -> B)에 관해 다음 노드로 정해 큐에 추가한다. A, B, C
무게가 동일한 노드에 방문한 이력이 있을 때는 추가하지 않는다. 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남긴다. 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 배열에 추가한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2251 {
// 6가지 이동하는 케이스를 표현하기 위한 배열
static int[] Sender = {0, 0, 1, 1, 2, 2};
static int[] Receiver = {1, 2, 0, 2, 0, 1};
static boolean visit[][]; // A, B의 무게만 있으면 C의 무게가 고정되므로 2개만 체크
static boolean[] answer;
static int[] now;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
now = new int[3]; // A, B, C 물의 양을 저장하는 배열
for(int i = 0; i < now.length; i++) {
now[i] = Integer.parseInt(st.nextToken());
}
visit = new boolean[201][201];
answer = new boolean[201];
BFS();
for(int i = 0; i < answer.length; i++) {
if(answer[i]) {
System.out.print(i + " ");
}
}
}
private static void BFS() {
Queue<AB> que = new LinkedList<>();
que.add(new AB(0, 0));
visit[0][0] = true;
answer[now[2]] = true;
while(!que.isEmpty()) {
AB p = que.poll();
int A = p.A;
int B = p.B;
int C = now[2] - A - B; // C는 전체 물의 양에서 A와 B를 뺀
for(int k = 0; k < 6; k++) { // A -> B, A -> C, B->A, B->C, C->A, C->B
int[] next = {A, B, C};
next[Receiver[k]] += next[Sender[k]];
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(!visit[next[0]][next[1]]) { // A와 B의 물의 양을 이용해 방문 배열 체크
visit[next[0]][next[1]] = true;
que.add(new AB(next[0], next[1]));
if(next[0] == 0) { // A의 물의 양이 0일 때 C의 물의 무게를 정답 변수에 저장
answer[next[2]] = true;
}
}
}
}
}
}
// AB 클레스 선언-> A와 B의 값만 지니고 있으면 C는 유추할 수 있으므로 두 변수만 사용하기
class AB {
int A;
int B;
public AB(int A, int B) {
this.A = A;
this.B = B;
}
}
문제점
처음 봤을 때 난의도가 골드 5인데 문제를 봤을 때 문제는 쉬워 보였다. 풀다가 BFS로 표현하고 탐색하는데 어려웠고 조건에 따라 무게 상태를 바꿔주는 방법을 떠올리지 못했다. 어려운 문제였고 복습으로 내 것으로 만들겠다.
오늘의 회고
오늘도 책 한 문제를 풀고 복습을 진행했습니다. 복습을 다 완료하기 전까지는 1문제 씩 풀려고 합니다. 백준)DFS까지 오늘은 복습을 진행하였습니다. 오늘 푼 문제는 어려운 문제였고 아직 갈 길이 멀다는 것을 느꼈습니다ㅠㅠ
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
| Do it! 알고리즘 코딩 테스트 (51번) (0) | 2022.06.10 |
|---|---|
| Do it! 알고리즘 코딩 테스트 (50번) (0) | 2022.06.09 |
| Do it! 알고리즘 코딩 테스트 (48번) (0) | 2022.06.07 |
| 백준) 그래프, 문자열 (0) | 2022.06.04 |
| Do it! 알고리즘 (36번 ~ 47번) (0) | 2022.06.03 |
