🙋🏻♀️ BFS이용 (보통의 방법과 다름!)
너무 어려워서 책 보고 따라 풀었다.
문제분석
지금까지 접해봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제!
A,B,C의 특정무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라 생각하고 문제에 접근하자.
로직
- 처음에 물통 A,B는 비어있고 C는 꽉 차 있으므로 최초 출발 노드를 (0,0,3번쨰 물통 용량)으로 초기화
- BFS 수행
BFS과정
1. 노드에서 갈 수 있는 6개의 경우(A->B, A->C, B->A, B->C, C->A, C->B)에 관해 다음 노드로 정해 큐에 추가한다. A,B,C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않는다.
2. 보내는 물통의 모든 옹량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다.단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남긴다.
3. 큐에 추가하는 시점에 1번째 물통의 무게가 0일때가 있으면 3번쨰 물통의 값을 정답 배열에 추가한다.
- 정답 리스트를 오름차순 출력한다.
제출코드
package chap08;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.util.Queue;
public class bucket49 {
static boolean visited[][];
static int[] sender = {0,0,1,1,2,2};
static int[] receiver = {1,2,0,2,0,1};
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];
now[0] = Integer.parseInt(st.nextToken());
now[1] = Integer.parseInt(st.nextToken());
now[2] = Integer.parseInt(st.nextToken());
visited = new boolean[201][201];
answer = new boolean[201];
BFS();
for(int i=0; i<answer.length; i++) {
if(answer[i]) System.out.print(i+ " ");
}
}
public static void BFS() {
Queue<AB> queue = new LinkedList<>();
queue.add(new AB(0,0));
visited[0][0] = true;
answer[now[2]] = true;
while(!queue.isEmpty()) {
AB p = queue.poll();
int A = p.A;
int B = p.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]];
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[next[0]][next[1]] = true;
queue.add(new AB(next[0], next[1]));
if(next[0] == 0) answer[next[2]] = true;
}
}
}
}
}
class AB {
int A;
int B;
public AB(int A, int B) {
this.A=A;
this.B=B;
}
}출처
Do it 알고리즘 코딩테스트 자바편
