[백준/JAVA] 2251번: 물통

🔺 문제

2251번: 물통

 

🔺 코드

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;
    }
}
 

✅ 해결 아이디어
✔ 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)의 값을 정답 배열에 추가

 

---

🔺 다른 풀이들

- 제일 설명이 깔끔하고 좋은 풀이👍👍👍👍

백준 2251 물통 Java

[백준] 2251번 물통문제 BFS로 풀어보기

 

- dfs & Set을 사용하셨다.

로그인

 

 

- 클래스 선언 안 하고 Queue 배열 사용하셨다.

boolean 배열 answer 사용하지 않고 ArrayList 만들어 거기에 값 추가하고, 리스트 정렬하고 출력하심

로그인

 

 

 

- 참고용

[문제] 백준 2251번 물통 자바

[백준] 2251번 물통 - Java

[java 백준] 실버 1/2251번 물통

---

💬 느낀 점

어렵당ㅇㅇ

 

 

 

1회독	2회독	3회독	4회독	5회독
V	6/21