14867번 : 물통 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(45분 30초)

아이디어

좋습니다.
요구하신 대로 아이디어(설계부터 코드 설명까지) 부분만 마크다운 형식으로 정리했습니다.
이 내용을 그대로 티스토리에 ## 아이디어 아래 붙여 넣으시면 됩니다.

---

아이디어

문제는 두 개의 물통 A, B가 주어졌을 때, 각각 최대 용량이 a, b일 때 목표 상태 (c, d)를 만드는 최소 횟수를 구하는 것이다.
이를 위해 BFS(너비 우선 탐색) 을 이용해 가능한 모든 상태를 탐색하며 방문처리는 10만 * 10만 배열을 만들기엔
메모리 낭비가 너무 심하기에 HashMap으로 a의 물의 양+" "+b의 물의 양의 문자열 key로 카운트를 value로 저장하여
방문처리 해준다

모든 가능한 물의 조합을 그래프 노드로 보고,
한 번의 조작을 간선으로 보는 방식으로 설계해서 풀어보았다.

설계

1. 상태 정의
   각 상태는 (x, y) 형태로,
   x: 현재 A 물통에 담긴 물의 양
   y: 현재 B 물통에 담긴 물의 양

2. 탐색 방법

   • BFS를 사용해 (0, 0) 상태에서 시작
   • 매 단계에서 가능한 모든 조작을 수행해 다음 상태를 큐에 추가
   • 이미 방문한 상태는 다시 방문하지 않도록 HashMap<String, Integer>로 관리
   • (c, d) 상태에 도달하면 탐색을 종료하고 그때의 이동 횟수를 출력

3. 가능한 조작

   • A 채우기 → (a, y)
   • B 채우기 → (x, b)
   • A 비우기 → (0, y)
   • B 비우기 → (x, 0)
   • A → B로 물 옮기기
   • B → A로 물 옮기기

   즉, 총 6가지 연산을 통해 새로운 상태를 만들 수 있다.

4. 방문 처리

   • 상태를 문자열 "x y"로 표현
   • visited 해시맵에 <"x y", 이동횟수> 형태로 저장
   • 이미 방문한 상태라도 더 적은 횟수로 도달 가능하다면 갱신

5. 종료 조건

   • 현재 상태 (x, y)가 (c, d)일 때 탐색 종료
   • 큐가 빌 때까지 찾지 못하면 -1 출력

---

코드 구조 및 동작 원리

1. 입력 처리

   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(br.readLine());
   a = Integer.parseInt(st.nextToken());
   b = Integer.parseInt(st.nextToken());
   c = Integer.parseInt(st.nextToken());
   d = Integer.parseInt(st.nextToken());

   • 네 개의 정수를 입력받아 각각 A, B의 최대 용량과 목표 상태 (c, d)를 저장한다.

2. BFS 준비

   ArrayDeque<int[]> q = new ArrayDeque<>();
   HashMap<String, Integer> visited = new HashMap<>();
   q.add(new int[]{0, 0});
   visited.put("0 0", 0);

   • 시작 상태 (0, 0)을 큐에 넣고 방문 처리한다.
   • visited에는 현재 상태까지의 이동 횟수를 기록한다.

3. BFS 탐색 루프

   while (!q.isEmpty()) {
       int[] cur = q.poll();
       int nowA = cur[0];
       int nowB = cur[1];
       int cnt = visited.get(nowA+" "+nowB);
       ...
   }

   • 큐에서 현재 상태를 꺼내고, 가능한 모든 다음 상태를 생성한다.
   • 새로 얻은 상태가 방문한 적이 없거나 더 적은 횟수로 도달 가능한 경우에만 큐에 추가한다.

4. 물 옮기기 함수(물 비우기, 물 채우기는 아래에 전체코드를 참고해주세요)

   static int [] moveWater(int x, int y, boolean naturalOrder)

   • naturalOrder == true면 A → B,
     false면 B → A 이동을 수행한다.

   • 예시 (A → B):

     int temp = y;
     y = Math.min(y+x, b);
     x -= y - temp;
     return new int[]{x, y};

     → A의 물이 B에 채워질 때까지 옮기며, 넘치지 않도록 최소값을 사용한다.

5. 결과 출력

   • 목표 (c, d)를 찾으면 이동 횟수 출력
   • 모든 경우를 탐색해도 찾지 못하면 -1 출력

---

핵심 포인트 정리

• BFS를 사용해 최소 이동 횟수를 보장
• 각 노드의 방문 상태를 visited HashMap을 통해 문자열 키로 관리해 중복 탐색 방지
• moveWater()로 물 옮기기 로직을 함수화하여 코드 가독성 확보
• 시간 복잡도는 상태 수(a*b)에 비례하므로 O(a*b) 수준

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int a, b, c, d;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        ArrayDeque<int []> q = new ArrayDeque<>();
        HashMap<String, Integer> visited = new HashMap<>();
        q.add(new int[]{0,0});
        visited.put(0+" "+0, 0);
        while (!q.isEmpty()){
            int [] cur = q.poll();
            int nowA = cur[0];
            int nowB = cur[1];
            int cnt = visited.get(nowA+" "+nowB);
            if(nowA==c&&nowB==d) {
                System.out.print(cnt);
                return;
            }
            //Fill x
            String fillAKey = a+" "+nowB;
            String fillBKey = nowA+" "+b;
            //a만 채우기
            if(!visited.containsKey(fillAKey)||visited.get(fillAKey)>cnt+1){
                q.add(new int[]{a, nowB, cnt+1});
                visited.put(fillAKey, cnt+1);
            }
            //b만 채우기
            if(!visited.containsKey(fillBKey)||visited.get(fillBKey)>cnt+1){
                q.add(new int[]{nowA, b, cnt+1});
                visited.put(fillBKey, cnt+1);
            }
            //Empty x
            String eraseAKey = 0+" "+nowB;
            String eraseBKey = nowA+" "+0;
            //a만 비우기
            if(!visited.containsKey(eraseAKey)||visited.get(eraseAKey)>cnt+1){
                q.add(new int[]{0, nowB, cnt+1});
                visited.put(eraseAKey, cnt+1);
            }
            //b만 비우기
            if(!visited.containsKey(eraseBKey)||visited.get(eraseBKey)>cnt+1){
                q.add(new int[]{nowA, 0, cnt+1});
                visited.put(eraseBKey, cnt+1);
            }
            //M(x, y)
            int [] moveXToY = moveWater(nowA, nowB, true);
            int [] moveYToX = moveWater(nowA, nowB, false);
            String moveFromAKey = moveXToY[0]+" "+moveXToY[1];
            String moveFromBKey = moveYToX[0]+" "+moveYToX[1];
            // x->y
            if(!visited.containsKey(moveFromAKey)||visited.get(moveFromAKey)>cnt+1){
                q.add(new int[]{moveXToY[0], moveXToY[1], cnt+1});
                visited.put(moveFromAKey, cnt+1);
            }
            // y->x
            if(!visited.containsKey(moveFromBKey)||visited.get(moveFromBKey)>cnt+1){
                q.add(new int[]{moveYToX[0], moveYToX[1], cnt+1});
                visited.put(moveFromBKey, cnt+1);
            }
        }
        System.out.print(-1);
    }
    static int [] moveWater(int x, int y, boolean naturalOrder){
        // a->b
        if(naturalOrder){
            int temp = y;
            y = Math.min(y+x, b);
            x -= y-temp;
            return new int []{x, y};
        }
        // b->a
        else{
            int temp = x;
            x = Math.min(x+y, a);
            y -= x-temp;
            return new int []{x, y};
        }
    }
}