반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
import java.util.*;
import java.io.*;
public class Main {
// 6가지 경우 탐색 위한 배열 선언
static int[] from = {0,0,1,1,2,2};
static int[] to = {1,2,0,2,0,1};
static boolean[][] visited; // 방문 배열
static boolean[] answer; // 정답 배열
static int[] now; // A,B,C 값 저장 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
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])
sb.append(i).append(" ");
}
System.out.println(sb);
}
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;
// A→B, A→C, B→A, B→C, C→A, C→B
for(int d = 0 ; d < 6 ; d++) {
int[] next = {A, B, C};
next[to[d]] += next[from[d]];
next[from[d]] = 0;
// 물이 넘칠 때
if(next[to[d]] > now[to[d]]) {
next[from[d]] = next[to[d]] - now[to[d]];
next[to[d]] = now[to[d]];
}
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;
}
}
}
}
}
}
// AB 클래스 선언
class AB {
int A;
int B;
public AB(int A, int B) {
this.A = A;
this.B = B;
}
}
|
cs |
✅ 해결 아이디어
✔ BFS / DFS
1) 노드에서 갈 수 있는 6개의 경우 (A → B, A → C, B → A, B → C, C → A, C → B)에 관해 다음 노드로 정해 큐에 추가
(A,B,C 무게가 동일한 노드에 방문한 이력이 있는 경우, 큐에 추가하지 않음)
2) 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다.
(단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남김)
3) 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통 (C)의 값을 정답 배열에 추가
🔺 다른 풀이들
- 제일 설명이 깔끔하고 좋은 풀이👍👍👍👍
- dfs & Set을 사용하셨다.
- 클래스 선언 안 하고 Queue 배열 사용하셨다.
boolean 배열 answer 사용하지 않고 ArrayList 만들어 거기에 값 추가하고, 리스트 정렬하고 출력하심
- 참고용
💬 느낀 점
어렵당ㅇㅇ
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 6/21 |
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1976번: 여행 가자 (0) | 2023.04.28 |
---|---|
[백준/JAVA] 1717번: 집합의 표현 (0) | 2023.04.28 |
[백준/JAVA] 1707번: 이분 그래프 (0) | 2023.04.27 |
[백준/JAVA] 1325번: 효율적인 해킹 (0) | 2023.04.27 |
[백준/JAVA] 18352번: 특정 거리의 도시 찾기 (0) | 2023.04.27 |